Đếm số cách leo lên bậc thang thứ n

Có n bậc thang. Một người sẽ đi từ bậc 1 đến bậc n. Số bậc tối đa mà anh/cô ấy có thể bước qua trong một bước cũng được cho. Với thông tin này, ta phải tìm các cách có thể để đi đến bậc thứ n.

Giả sử người đó có thể bước tối đa hai bậc mỗi bước. Ta có thể tìm mối quan hệ đệ quy để giải bài toán này. Người đó có thể đến bậc n, hoặc từ bậc (n-1) hoặc từ bậc (n-2). Vậy ways(n) = ways(n-1) + ways(n-2).

Đầu vào và Đầu ra

Đầu vào: Số bậc thang, ví dụ 10. Số bậc tối đa có thể nhảy trong một bước, ví dụ 2.
Đầu ra: Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

Thuật toán

stairClimbWays(stair, max)
Đầu vào: Số bậc thang, số bậc nhảy tối đa trong một bước.
Đầu ra: Số cách có thể để đến đích.
Bắt đầu
  định nghĩa mảng count kích thước bằng số bậc thang
  count[0] := 1
  count[1] := 1
  với i := 2 đến stair - 1, làm
    count[i] := 0
    với j = 1 đến i và j <= max; làm
      count[i] := count[i] + count[i - j]
    kết thúc
  kết thúc
  trả về count[stair - 1]
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

int stairClimbWays(int stair, int max) {
  int count[stair]; // điền kết quả bậc thang theo cách bottom-up
  count[0] = 1; // khi có 0 hoặc 1 bậc, 1 cách leo
  count[1] = 1;
  
  for (int i = 2; i < stair; i++) {
    // cho bậc 2 trở lên
    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) {
  // người có thể leo 1,2,...max bậc tại một thời điểm
  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);
}

Đầu ra

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