假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 2 阶 + 1 阶
解：这道题就是典型入门级别的动态规划问题。但是我现在比较模糊，貌似每一个问题如果能用递归去解决的话，都是自上而下的方向进行解题。貌似与动态规划的方向相反了。下面是两者的区别
不同点：
1，分治法往往用到递归计算，自上而下计算，而动态规划则直接自底向上计算
2，分治大的小问题在递归的过程中可能会被反复计算，动态规划中的小问题计算后被存储，下次再碰到时直接调用、
3，分治法的小问题的解只使用一次，动态规划的小问题的解存储以备大问题求解时反复调用
下面再来说一下解题
n=1：只能走一步
n=2：能走两个一步。能走一个两步
n=3：第一步只能是走一步，第二步可以走1个两步，或者 两个一步
当n=4,5,6的时候，可以发现当前步拥有的种类数就是前两步拥有种类数的和，
也就是 f(n) = f(n-1)+f(n-2);
所以我们从第三步开始，因为前两步其实是固定的
再者，我们用一个vector去记录以往的每一步数自身所拥有多少种情况
class Solution { public: int climbStairs(int n) { vector<int> result; result.push_back(1); result.push_back(2); for(int i = 3;i <= n;i++){ result.push_back(result[i-2]+result[i-3]); } return result[n-1]; } }; 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/121567.html