Bài toán leo cầu thang

Có bao nhiêu cách khác nhau để bạn có thể leo lên đỉnh cầu thang có n bậc nếu mỗi lần chỉ được leo 1 hoặc 2 bậc?

Ví dụ 1:

Đầu vào: n = 2

Đầu ra: 2

Giải thích: Để leo lên đỉnh cầu thang có 2 bậc, bạn có thể leo mỗi lần 1 bậc hai lần hoặc leo liền 2 bậc. Vậy có 2 cách khác nhau để leo lên đỉnh.

Ví dụ 2:

Đầu vào: n = 3

Đầu ra: 3

Giải thích: Để leo lên đỉnh cầu thang có 3 bậc, bạn có thể leo mỗi lần 1 bậc ba lần, leo 1 bậc rồi 2 bậc, hoặc leo 2 bậc rồi 1 bậc. Vậy có 3 cách khác nhau để leo lên đỉnh.

Ví dụ 3:

Đầu vào: n = 4

Đầu ra: 5

Giải thích: Để leo lên đỉnh cầu thang có 4 bậc, có 5 cách sau: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. Mỗi số biểu thị số bậc bạn leo mỗi lần, có thể là 1 hoặc 2, và thứ tự các bước leo rất quan trọng.