Leo cầu thang trong C++ (Climbing Stairs)

Có n bậc thang. Người đi từ bậc 1 đến n. Số bậc tối đa mỗi bước cũng cho trước. Tìm số cách đi đến bậc n. Nếu tối đa 2 bậc/bước: ways(n) = ways(n-1) + ways(n-2) (dãy Fibonacci).

Ví dụ

Số bậc = 10, tối đa 2 bậc/bước → 89 cách.

Thuật toán Quy hoạch động

1. Mảng count kích thước số bậc
2. count[0] = 1, count[1] = 1
3. Với i = 2 đến stair-1:
   • count[i] = 0
   • Với j = 1 đến min(max, i): count[i] += count[i-j]
4. Trả về count[stair-1]

Chương trình C++

#include <iostream> 
using namespace std; 

int stairClimbWays(int stair, int max) {
    int count[stair];
    count[0] = 1;
    count[1] = 1;
    for (int i = 2; i < stair; i++) {
        count[i] = 0;
        for (int j = 1; j <= max && j <= i; j++)
            count[i] += count[i - j];
    }
    return count[stair - 1];
}

int countWays(int stair, int max) {
    return stairClimbWays(stair + 1, max);
}

int main() {
    int stair, max;
    cout << "Enter number of stairs: "; cin >> stair;
    cout << "Enter max stair a person can climb: "; cin >> max;
    cout << "Number of ways to reach: " << countWays(stair, max);
}

Kết quả

Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

Giải thích

Với max=2: đây là dãy Fibonacci. Với max=3: dãy Tribonacci. Tổng quát: ways(n) = Σ ways(n-i) với i=1..max.