Mendaki Tangga

Berapa banyak cara berbeda yang dapat kamu gunakan untuk mencapai puncak tangga dengan n anak tangga jika kamu hanya boleh menaiki 1 atau 2 anak tangga sekaligus?

Contoh 1:

Input: n = 2

Output: 2

Penjelasan: Untuk mencapai puncak tangga dengan 2 anak tangga, kamu dapat menaiki 1 anak tangga sebanyak dua kali atau menaiki 2 anak tangga sekaligus. Jadi, ada 2 cara berbeda untuk mencapai puncak.

Contoh 2:

Input: n = 3

Output: 3

Penjelasan: Untuk mencapai puncak tangga dengan 3 anak tangga, kamu dapat menaiki 1 anak tangga sebanyak tiga kali, menaiki 1 anak tangga lalu 2 anak tangga, atau menaiki 2 anak tangga lalu 1 anak tangga. Jadi, ada 3 cara berbeda untuk mencapai puncak.

Contoh 3:

Input: n = 4

Output: 5

Penjelasan: Untuk mencapai puncak tangga dengan 4 anak tangga, berikut 5 pilihannya: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. Setiap angka menunjukkan menaiki 1 atau 2 anak tangga sekaligus, dan urutannya berpengaruh.