Khóa học Python từ Cơ bản đến Nâng cao

Bài 11.3 - Staircase Problem - Bài toán kinh điển

Bạn đang đứng ở chân cầu thang có n bậc, và mỗi lần bạn có thể bước 1 hoặc 2 bậc. Nhiệm vụ là tìm bao nhiêu cách khác nhau để leo lên đến bậc thứ n.

Đây là một trong những bài toán kinh điển nhất giúp bạn làm quen với quy hoạch động (Dynamic Programming) và tư duy đệ quy. Bài toán này còn có liên hệ trực tiếp đến dãy Fibonacci, cực kỳ phổ biến trong nhiều thuật toán.

Mô tả bài toán

Cho một số nguyên n, đại diện cho số bậc cầu thang. Viết một hàm climb_stairs(n) trả về số cách để leo đến bậc thứ n, biết rằng mỗi lần có thể bước lên 1 hoặc 2 bậc.

Ví dụ:

• n = 1 → 1 cách ([1])
• n = 2 → 2 cách ([1+1], [2])
• n = 3 → 3 cách ([1+1+1], [1+2], [2+1])

Phân tích bài toán

Hãy xem xét bậc thứ n. Để đến được bậc n, ta chỉ có 2 khả năng:

• Bước từ bậc n-1 lên 1 bậc.
• Hoặc bước từ bậc n-2 lên 2 bậc.

Vậy nên:

Số cách để đến bậc n = cách đến (n-1) + cách đến (n-2)

Đây chính là công thức đệ quy của dãy Fibonacci!

Cách 1: Đệ quy đơn giản (nhưng rất chậm)

def climb_stairs(n):
    if n <= 2:
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)

Nhược điểm:

• Rất nhiều lời gọi hàm bị lặp lại (ví dụ climb_stairs(3) bị gọi nhiều lần).
• Độ phức tạp thời gian: O(2^n) — quá lớn khi n > 30.

Cách 2: Dùng mảng dp – Quy hoạch động cơ bản

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Ưu điểm:

• Không bị lặp lại phép tính, vì đã lưu trữ kết quả.
• Độ phức tạp thời gian: O(n).
• Bộ nhớ: O(n).

Cách 3: Tối ưu bộ nhớ chỉ dùng 2 biến

Chúng ta chỉ cần giữ 2 giá trị cuối cùng là đủ:

def climb_stairs(n):
    if n <= 2:
        return n

    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b

    return b

Ưu điểm:

• Tối ưu bộ nhớ: chỉ dùng O(1).
• Nhanh và gọn.

Ví dụ minh hoạ chi tiết

Ví dụ 1:

print(climb_stairs(2))  # Output: 2

Giải thích: Có 2 cách để leo: [1+1] và [2].

Ví dụ 2:

print(climb_stairs(3))  # Output: 3

Giải thích: [1+1+1], [1+2], [2+1]

Ví dụ 3:

print(climb_stairs(5))  # Output: 8

Giải thích: Có tổng cộng 8 cách để leo lên bậc thứ 5:

1. [1+1+1+1+1]
2. [1+1+1+2]
3. [1+1+2+1]
4. [1+2+1+1]
5. [2+1+1+1]
6. [1+2+2]
7. [2+1+2]
8. [2+2+1]

So sánh các cách tiếp cận

Biến thể thú vị hơn

Bạn có thể mở rộng bài toán như sau:

Leo 1, 2 hoặc 3 bậc mỗi lần

def climb_stairs_extended(n):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    return (climb_stairs_extended(n - 1) +
            climb_stairs_extended(n - 2) +
            climb_stairs_extended(n - 3))

Hoặc bước theo mảng bất kỳ

Ví dụ: Chỉ được bước [1, 3, 5] bậc mỗi lần → gọi là bài toán Generalized Staircase.

Kết luận

Bài toán Staircase là một ví dụ đơn giản nhưng cực kỳ hiệu quả để học cách:

• Nhận ra cấu trúc đệ quy.
• Tối ưu bằng quy hoạch động.
• Tiết kiệm bộ nhớ hiệu quả.

Nếu bạn hiểu bài này, bạn sẽ dễ dàng tiếp cận các bài toán như:

• Fibonacci
• Climbing Stairs with Restrictions
• Coin Change (biến thể)
• DP on Trees/Graphs