Leo Cầu ThangClimbing Stairs
Hiểu bài
Bạn đang leo một cầu thang có n bậc. Mỗi lần bạn có thể bước 1 hoặc 2 bậc. Có bao nhiêu cách khác nhau để bạn leo lên đến bậc thứ n?
Ví dụ:
n = 2
output = 2 // [1+1] hoặc [2]
n = 3
output = 3 // [1+1+1], [1+2], [2+1]Quan sát: số cách leo lên bậc n = số cách leo lên bậc n-1 (rồi bước 1) + số cách leo lên bậc n-2 (rồi bước 2).
Đây chính là quan hệ truy hồi Fibonacci — bài nhập môn của Quy hoạch động 1 chiều (DP-1D).
Xem cách cơ bản (chậm hơn)
O(2ⁿ) time, O(n) space (call stack)function climbStairs(n: number): number {
// Đệ quy thuần — mỗi bước gọi 2 nhánh con
if (n <= 1) return 1
return climbStairs(n - 1) + climbStairs(n - 2)
}Cây đệ quy có 2 nhánh ở mỗi node, độ sâu n → O(2ⁿ) phép tính.
Nhiều bài toán con được tính lại nhiều lần — đây là lý do cần Quy hoạch động.
Lời giải tối ưu
O(n) time, O(n) spacefunction climbStairs(n: number): number {
if (n <= 1) return 1
const dp = new Array<number>(n + 1)
dp[0] = 1 // 1 cách để đứng tại bậc 0 (không leo)
dp[1] = 1 // 1 cách để leo lên bậc 1
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] // quan hệ truy hồi
}
return dp[n]
}Lưu kết quả từng bậc vào mảng dp để không tính lại.
Mỗi dp[i] chỉ cần 2 giá trị trước — có thể tối ưu thêm xuống O(1) space bằng 2 biến thay vì cả mảng.
Chạy thử từng bước
- 1
n=5.
Khởi tạo dp[0]=1, dp[1]=1.
dp:[1,1,"?","?","?","?"] - 2
i=2: dp[2] = dp[1]+dp[0] = 1+1 = 2.
i:2dp:[1,1,2,"?","?","?"] - 3
i=3: dp[3] = dp[2]+dp[1] = 2+1 = 3.
i:3dp:[1,1,2,3,"?","?"] - 4
i=4: dp[4] = dp[3]+dp[2] = 3+2 = 5.
i:4dp:[1,1,2,3,5,"?"] - 5
i=5: dp[5] = dp[4]+dp[3] = 5+3 = 8.
Kết quả: dp[5]=8.
i:5dp:[1,1,2,3,5,8]result:8
Trường hợp biên phải nhớ
n=0 — đứng ngay ở đích, 1 cách (không leo).
n=1 — 1 cách duy nhất: bước 1 bậc.
n lớn (ví dụ n=45) — kết quả là số Fibonacci thứ 46 (1.836.311.903), vẫn nằm trong safe integer của JavaScript (~2⁵³).
Tối ưu space: thay dp[] bằng 2 biến
prevvàcurr, tiết kiệm O(n) space xuống O(1).