There are n steps for the stairs. You can go up to the first, second, and third steps in one step. How many different ways are there to calculate the program?

topic:There are n steps in the stairs. You can go up to the first, second, and third steps in one step. Programming and calculation of how many different ways to walk are there.？

For such a question,

Idea: Suppose the number of walking methods of n steps is f(n). If there is only 1 step, there are 1 way of walking (one step up to one step), that is f(1)=1; if there are 2 steps, there are 2 ways of walking (one is to go up to the first level, then to the first level, and the other is to go up to the second level in one step), that is f(2)=2; if there are 3 steps, there are 4 ways of walking (one is to go up to the first level each time, there are one; the other is 2+1, there are two; the third is 3, there are 1 type in total), that is, f(3)=4;

When there are n steps (n>3), we will reduce the scale of the problem. You can think of it like this: if you go up one step in one step, you will go up n-1 steps before, and the way you walk is f(n-1), and if you go up two steps in one step, you will go up n-2 steps before, and the way you walk is f(n-2), so f(n)=f(n-1)+f(n-2). The listed recursive equations are: 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

The last step may be to go up from the n-1st level up, from the n-2nd level up, or from the n-3rd level up, or from the n-3rd level up. Therefore, the way to reach the last level is actually the sum of the ways to reach the last third level.

Solution 1: Follow the idea of ​​recursion; but the calculation time is very long

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

You only need to solve the sub-problem once, and then encounter it later and call it directly, so we create a new array to store the results of the sub-problem:

The array element is initially zero. If it is a new sub-problem, we solve it and assign the result to the corresponding array element; in this way, when we encounter the same sub-problem again, we can call it directly.

int countWaysDP(int n, dp[])
  { if (n<0)
     return 0;
    if (n==0)
    return dp[n];
    if (dp[n]>0)
    return dp[n]; //If it is greater than 0, it means that this sub-problem has been calculated, and the array is called directly
    else {
    dp[n]=countWays[n-1,dp]+countWays[n-2,dp]+countWays[n-3,dp]; // Otherwise, the array needs to be calculated
    return dp[n]; }
 }

#include<iostream>
 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]; //If it is greater than 0, it means that this sub-problem has been calculated, and the array is called directly
     else {
     dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp); // Otherwise, the array needs to be calculated
     return dp[n]; }
 }
    int main() {
     int m[MAX]={0};
      // int m[MAX];
    for(int i=1;i<10;i++)
    cout<<countWaysDP(i,m)<<endl;
   }