Lanjut50 XPUnit 13: Pemrograman Dinamis, soal 1 dari 10
Cara Naik Tangga
Hitung banyaknya cara menaiki N anak tangga satu atau dua langkah sekaligus.
Setiap pagi Raka menaiki tangga menuju kelasnya di lantai tiga. Kadang ia melangkah satu anak tangga, kadang langsung dua. Ada berapa urutan langkah berbeda untuk menaiki N anak tangga?
Masukan
Satu bilangan bulat N dari 1 sampai 70.
Keluaran
Banyaknya urutan langkah yang berbeda.
Contoh masukan dan keluaran
Contoh 1
Masukan
4
Keluaran
5
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Untuk tiba di anak tangga ke-N, langkah terakhir Raka pasti dari anak tangga N-1 atau N-2.
Petunjuk 2
Jadi cara(N) = cara(N-1) + cara(N-2). Hitung dari bawah, mulai dari cara(1) = 1 dan cara(2) = 2.