Climbing Stairs

Bài toán

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

Ví dụ:

Input: n = 2
Output: 2
Cách: (1, 1), (2)

Input: n = 3
Output: 3
Cách: (1, 1, 1), (1, 2), (2, 1)

Phân Tích & Tiếp Cận

1. Identify DP Problem

Tại bậc thang thứ i, ta chỉ có thể đến đó từ bậc i-1 (bước 1 bước) hoặc bậc i-2 (bước 2 bước). Vậy số cách để đến bậc i chính là tổng số cách đến bậc i-1 cộng với số cách đến bậc i-2. Công thức truy hồi (Recurrence Relation): dp[i] = dp[i-1] + dp[i-2].

2. Base Cases

• Bậc 0: 1 cách (đứng yên).
• Bậc 1: 1 cách (từ 0 lên 1).
• Bậc 2: 2 cách.

3. Space Optimization (Tối ưu không gian)

Ta thấy dp[i] chỉ phụ thuộc vào 2 giá trị trước đó. Vậy không cần lưu mảng n phần tử, chỉ cần 2 biến one (đại diện i-1) và two (đại diện i-2). Đây chính là dãy Fibonacci.

function climbStairs(n: number): number {
    let one = 1; // Cách để đến bậc n-1
    let two = 1; // Cách để đến bậc n-2

    for (let i = 0; i < n - 1; i++) {
        const temp = one;
        one = one + two;
        two = temp;
    }

    return one;
}

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

Pattern Nhận Diện

• Bài toán đếm số cách (Count ways).
• Quyết định tại bước hiện tại phụ thuộc vào các bước ngay trước đó.
• Cấu trúc con tối ưu (Optimal Substructure) & Bài toán con gối nhau (Overlapping Subproblems).