นับวิธีเดินบันได (Count Ways to Reach n-th Stair)

มีบันได n ขั้น คนเดินจากขั้นที่ 1 ถึงขั้นที่ n กำหนดจำนวนขั้นสูงสุดที่ข้ามได้ใน 1 ก้าว (max) ต้องการหาจำนวนวิธีเดินขึ้นไปถึงขั้นที่ n

เช่น max = 2: ways(n) = ways(n-1) + ways(n-2) (เหมือน Fibonacci)

การรับค่าและแสดงผล

Input: จำนวนขั้น = 10, ขั้นสูงสุดต่อก้าว = 2
Output: Number of ways to reach: 89

อัลกอริทึม

stairClimbWays(stair, max) - Bottom-Up DP

Begin
  กำหนดอาร์เรย์ count ขนาด stair
  count[0] := 1, count[1] := 1
  
  for i := 2 ถึง stair-1 do
    count[i] := 0
    for j := 1 ถึง min(i, max) do
      count[i] := count[i] + count[i-j]
    done
  done
  
  return count[stair-1]
End

ตัวอย่างโค้ด (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);
}

ผลลัพธ์

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