n番目の階段に到達する方法を数える

各ステップで最大2つの階段を越えることができると考えてみましょう。したがって、この問題を解決するための漸化式を見つけることができます。 （n-1）番目の階段または（n-2）番目の階段のいずれかからn番目の階段に移動できます。つまり、ways（n）=Ways（n-1）+ Ways（n-2）。

入力と出力

Input:
The number of stairs, say 10 the maximum number of stairs that can be jumped in one step, say 2
Output:
Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

アルゴリズム

stairClimpWays(stair, max)

入力- 階段の数、1つのステップでの最大階段ジャンプ。

出力- 到達するための可能な方法の数。

Begin
   define array count of size same as stair number
   count[0] := 1
   count[0] := 1

   for i := 2 to stair -1, do
      count[i] := 0
      for j = 1 to i and j <= max; do
         count[i] := count[i] + count[i - j]
      done
   done
   return count[stair - 1]
End

例

#include<iostream>
using namespace std;

int stairClimbWays(int stair, int max) {
   int count[stair];    //fill the result stair using bottom up manner
   count[0] = 1;       //when there are 0 or 1 stair, 1 way to climb
   count[1] = 1;
   
   for (int i=2; i<stair; i++) {    //for stair 2 to higher
      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) {    //person can climb 1,2,...max stairs at a time
   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