階段にはn段の階段があり、上の階に上がると1段、2段、3段に上がることができ、プログラム計算には何種類の異なる歩き方がありますか?

テーマ:階段はn段の階段があって、上の階は1段、2段、3段に上がることができて、プログラムを編んで計算して全部で何種類の異なる歩き方がありますか?
 
このような問題に対して、
構想:n段階段の歩き方数をf(n)とする.1つの階段しかない場合、歩き方は1種類(一歩上1つの階段)、すなわちf(1)=1である.2つの階段がある場合、歩き方は2種類ある(1つは1階、さらに1階、もう1つは1歩2階)、すなわちf(2)=2;3つの階段がある場合、歩き方は4種類(1つは1階ごとに1種類、もう1つは2+1で2種類、3つ目は3で1種類)、すなわちf(3)=4である.
n個の段差(n>3)がある場合,問題規模を縮小し,最後に1段上に上がるとn−1段上に上がり,f(n−1)+f(n−2)種,最後に2段上に上がるとn−2段上に上がり,f(n)=f(n−1)+f(n−2)種と考える.リストされた再帰方程式は、f(1)=1である.f(2)=2;
f(3)=4;
if(n==1)
return 1;
else if(n==2)
return 2;
else if(n==3)
return 4;
else
return  f(n-1)+f(n-2)+f(n-3),n>3
最後のステップは、n−1次から1次、n−2次から2次、またはn−3次から3次である可能性がある.そのため、最後の階に着く歩き方は、実はこの最後の3階に着く方法の総和です.
解決方法1:再帰的な考え方に従う;演算時間が長い
 

int countWays (int n)
{if (n<=0)
   return 0;
if (n==1)
   return 1;
else if(n==2)
   return 2;
else if(n==3)
   return 4;
else
  {
  return countWays(n-1)+countWays(n-2)+countWays(n-3);
 }
}   

 
 
解決方法2:動的計画の思想最適化を採用し、
一つの問題がいくつかの重複するサブ問題に分解できる場合、動的計画の思想を運用する.

           ，     ，    ，                    ：

 

         ，       ，    ，             ；               ，        。

int countWaysDP(int n, dp[])
 { if (n<0) 
    return 0; 
   if (n==0) 
   return dp[n]; 
   if (dp[n]>0) 
   return dp[n]; //    0             ，       
   else { 
   dp[n]=countWays[n-1,dp]+countWays[n-2,dp]+countWays[n-3,dp]; //           
   return dp[n]; } 
}

次に実際の実行コードを貼りましょう.

#include 
using namespace std; 
const int MAX=1000; 
int countWays(int n) {
   if (n<0) 
     return 0; 
   if (n==0) 
      return 1; 
    else { 
  return countWays(n-1)+countWays(n-2)+countWays(n-3); 
  } 
} 

int countWaysDP(int n, int dp[]) {
    if (n<0) 
    return 0; 
    if (n==0) 
    return 1; 
    if (dp[n]>0) 
    return dp[n]; //    0             ，       
    else { 
    dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp); //           
    return dp[n]; } 
} 
   int main() { 
    int m[MAX]={0}; 
     // int m[MAX]; 
   for(int i=1;i<10;i++) 
   cout<