Climbing Stairs

Đề bài

Bạn đang leo một cầu thang. Cần n bước để lên đến đỉnh.

Mỗi lần bạn có thể leo 1 hoặc 2 bước. Có bao nhiêu cách khác nhau để bạn leo lên đỉnh?

Ví dụ

Ví dụ 1:

Input: n = 2
Output: 2
Giải thích: Có 2 cách leo lên đỉnh.
1. 1 bước + 1 bước
2. 2 bước

Ví dụ 2:

Input: n = 3
Output: 3
Giải thích: Có 3 cách leo lên đỉnh.
1. 1 bước + 1 bước + 1 bước
2. 1 bước + 2 bước
3. 2 bước + 1 bước

Ràng buộc

• 1 <= n <= 45