算法-有n步台阶，一次只能上1步或2步，共有多少种走法

深碍√TFBOYSˉ_ 2022-03-08 07:55 232阅读 0赞

[https://blog.csdn.net/w8452960/article/details/79216847][https_blog.csdn.net_w8452960_article_details_79216847]

# 分析 #

1、n=0 和 n=1 的时候 并没有其他可选择的，所以可以得出f(0)=0;f(1)=1;   
2、n>=2时情况就变复杂起来，但是这个时候可以操作的步骤也就2种   
也就是走1步(n-1)与走2步(n-2)。所以可以得到f(n)=f(n-1)+f(n-2);   
从当前状态转为下一状态的通用算法既可。   
3、 验证，使用2以上的数字验证几次。

# 实现 #

实现算法往往是简单的，及时是复杂算法也花费不了太多精力，所以将问题转换为数学问题是一种很好的选择。当前这种简单算法实现方式更为简单，而且往往不止一种方式。

## 递归 ##

public static int f(int n){
        if(n<=2) return n;
        int x = f(n-1)+f(n-2);
        return x;
    }

优点：可能是最好理解的算法了把。代码简单，好理解。   
缺点：计算次数颇多，有很多冗余计算。

## 迭代 ##

public static int f(int n){
        if(n<=2) return n;
        if first=1,second=2;
        int third=0;
        for(int i=3;i<=n;i++){
            third = first+second;
            first = second;
            second = third;
        }
        return third;
    }

优点: 基本没有冗余计算，效率高   
缺点: 谁能一次读完就理解的？

## 动态规划 ##

> 原文：动态规划是解决下面这些性质类问题的技术：   
> 1. 一个问题可以通过更小子问题的解决方法来解决（译者注：即问题的最优解 包含了其子问题的最优解，也就是最优子结构性质）。   
> 2. 有些子问题的解可能需要计算多次（译者注：也就是子问题重叠性质）。   
> 3. 子问题的解存储在一张表格里，这样每个子问题只用计算一次。   
> 4. 需要额外的空间以节省时间。

public static int[] A = new int[100];
    public static int f(int n){
        if(n<=2){
            A[n] = n;
        }
        if(A[n]>0){
            return A[n];
        } else {
            A[n] = f(n-1)+f(n-2);
            return A[n];
        }
    }

虽然没弄懂为啥叫动态规划，但是代码还是很清晰的。   
优点：已经计算过的结果就不需要再次计算了。空间换时间   
缺点：需要额外的开销。

# 楼梯有n阶台阶，上楼可以一步上1阶,2阶，3阶，编程序计算共有多少种不同的走法？ #

2017年09月23日 23:35:09 [圆觉\_][Link 1] 阅读数：2980 标签： [C++][C][递归][Link 2][动态规划][Link 3][编程][Link 4] 更多

个人分类： [C/C++][C_C]

[https://blog.csdn.net/sinat\_28296297/article/details/78074427][https_blog.csdn.net_sinat_28296297_article_details_78074427]

`题目：楼梯有n阶台阶，上楼可以一步上1阶,2阶，3阶，编程序计算共有多少种不同的走法？`

`对于这样一个问题，`

`思路：设n阶台阶的走法数为f(n)。如果只有1个台阶，走法有1种（一步上1个台阶），即f(1)=1；如果有2个台阶，走法有2种（一种是上1阶，再上1阶，另一种是一步上2阶），即f(2)=2；如果有3个台阶，走法有4种（一种每次1阶，共一种；另一种是2+1，共两种；第三种是3，共1种），即f(3)=4；`

`当有n个台阶（n>3）时，我们缩小问题规模，可以这样想：最后是一步上1个台阶的话，之前上了n-1个台阶，走法为f(n-1)种，而最后是一步上2个台阶的话，之前上了n-2个台阶，走法为f(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阶。因此，抵达最后一阶的走法，其实就是抵达这最后三阶的方式的总和。`

`解决方法1：按照递归的思想；但运算时间很长`

1.  `int countWays (int n)`
2.  `{if (n<0)`
3.  `return 0;`
4.  `if (n==0)`
5.  `return 1;`
6.  `else`
7.  `{`
8.  `return countWays(n-1)+countWays(n-2)+countWays(n-3);`
9.  `}`
10. `}`

解决方法2：采用动态规划的思想 优化，

当一个问题可以分解成若干重复的子问题时，运用动态规划的思想：

只需要将子问题求解一次，以后再遇到，直接调用，所以我们新建一个数组用于存储子问题的结果：

将数组元素初始为零，若为新的子问题，我们求解，并把结果赋给对应的数组元素；这样当我们再次遇到相同的子问题，就可以直接调用了。

1.  `int countWaysDP(int n, dp[])`
2.  `{`
3.  `if (n<0)`
4.  `return 0;`
5.  `if (n==0)`
6.  `return dp[n];`
7.  `if (dp[n]>0)`
8.  `return dp[n]; //如果大于0 说明这个子问题已经计算过，直接调用数组`
9.  `else`
10. `{ dp[n]=countWays[n-1,dp]+countWays[n-2,dp]+countWays[n-3,dp]; //否则 还需计算该数组`
11. `return dp[n];`
12. `}`
13. `}`

接下来贴上实际运行代码吧；

1.  `#include<iostream>`
2.   
3.  `using namespace std;`
4.  `const int MAX=1000;`
5.  `int countWays(int n)`
6.  `{if (n<0)`
7.  `return 0;`
8.  `if (n==0)`
9.  `return 1;`
10. `else`
11. `{`
12. `return countWays(n-1)+countWays(n-2)+countWays(n-3);`
13. `}`
14. `}`
15.  
16. `int countWaysDP(int n, int dp[])`
17. `{`
18. `if (n<0)`
19. `return 0;`
20. `if (n==0)`
21. `return 1;`
22. `if (dp[n]>0)`
23. `return dp[n]; //如果大于0 说明这个子问题已经计算过，直接调用数组`
24. `else`
25. `{ dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp); //否则 还需计算该数组`
26. `return dp[n];`
27. `}`
28. `}`
29. `int main()`
30. `{`
31. `int m[MAX]={0};`
32. `// int m[MAX];`
33. `for(int i=1;i<10;i++)`
34. `cout<<countWaysDP(i,m)<<endl;`
35. `}`

[https_blog.csdn.net_w8452960_article_details_79216847]: https://blog.csdn.net/w8452960/article/details/79216847
[Link 1]: https://me.csdn.net/sinat_28296297
[C]: http://so.csdn.net/so/search/s.do?q=C++&t=blog
[Link 2]: http://so.csdn.net/so/search/s.do?q=%E9%80%92%E5%BD%92&t=blog
[Link 3]: http://so.csdn.net/so/search/s.do?q=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&t=blog
[Link 4]: http://so.csdn.net/so/search/s.do?q=%E7%BC%96%E7%A8%8B&t=blog
[C_C]: https://blog.csdn.net/sinat_28296297/article/category/7152368
[https_blog.csdn.net_sinat_28296297_article_details_78074427]: https://blog.csdn.net/sinat_28296297/article/details/78074427