C++で階段を上る

n段あります。 1人目からn番目の階段に行きます。彼/彼女が1つのステップで横断できる階段の最大数も与えられます。この情報を使用して、n番目の階段に行くための可能な方法を見つける必要があります。各ステップで最大2つの階段を越えることができると考えてみましょう。したがって、この問題を解決するための漸化式を見つけることができます。 （n-1）番目の階段または（n-2）番目の階段のいずれかからn番目の階段に移動できます。つまり、ways（n）=Ways（n-1）+ Ways（n-2）。

階段の数（たとえば10）、1つのステップでジャンプできる階段の最大数（たとえば2）を想定すると、出力は89の可能な方法になります。

これを解決するには、次の手順に従います-

• 階段番号と同じサイズの配列数を定義します
• 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]
• リターンカウント[階段-1]

理解を深めるために実装を見てみましょう

例（C ++）

#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);
}

入力

Stairs = 10
Max stairs a person can climb: 2

出力

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