Có n bậc thang, người đứng dưới cầu thang muốn đi lên trên cùng. Họ có thể lựa chọn bước 1 hoặc 2 bậc tại một thời điểm. Đếm số cách mà một người có thể đi lên trên cầu thang.
Đây là một bài toán thú vị vì có nhiều cách để giải nó, dưới đây là minh hoạ của các giải pháp lập trình khác nhau.
- Phá Mã - Thời gian:
O(2^n); Không gian:O(1) - Dùng Bộ Nhớ Phụ - Thời gian:
O(n); Không gian:O(n) - Quy Hoạch Động - Thời gian:
O(n); Không gian:O(n) - Vòng Lặp - Time:
O(n); Space:O(1)