Nhấn vào đây để đọc bằng ngôn ngữ khác: English
Có n bậc cầu thang, một người đứng ở dưới muốn đến đỉnh. Người đó có thể leo 1 hoặc 2 bậc cầu thang mỗi lần. Đếm số cách mà người đó có thể đến được đỉnh.
Đây là một vấn đề thú vị vì có nhiều cách để giải quyết mà minh họa các phương pháp lập trình khác nhau.
- Giải Pháp Đệ Quy Brute Force - Thời gian:
O(2^n); Không gian:O(1) - Giải Pháp Đệ Quy Với Ghi Nhớ - Thời gian:
O(n); Không gian:O(n) - Giải Pháp Lập Trình Động - Thời gian:
O(n); Không gian:O(n) - Giải Pháp Lặp - Thời gian:
O(n); Không gian:O(1)