爬楼梯
动态规划
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
我们来分析一下，动规五部曲：
定义一个一维数组来记录不同楼层的状态
确定dp数组以及下标的含义
dp[i]： 爬到第i层楼梯，有dp[i]种方法
从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。
我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。
所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
class Solution { public: int climbStairs(int n) { if(n<=2) return n; vector<int> dp(n+1); dp[1] = 1; dp[2] = 2; for(int i=3 ;i<dp.size() ; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } };
完全背包
可以转换为完全背包，求排序数的问题
目标值就是楼梯的高度n，价值就是步子的高度1，2
class Solution { public: int climbStairs(int n) { vector<int> step = {1,2}; vector<int> dp(n+1,0); dp[0] = 1; //求排序数，先遍历背包，后遍历价值 for(int j=0 ; j<=n ;j++) { for(int i=0 ; i<step.size();i++) { if(j>=step[i]) { dp[j] += dp[j-step[i]]; } else dp[j] = dp[j]; } } return dp[n]; } };
二刷
class Solution { public: int climbStairs(int n) { if(n<=2) return n; vector<int> dp(n+1,0); dp[1] = 1; dp[2] = 2; for(int i=3 ; i<=n ; i++) { dp[i] = dp[i-1] + dp[i-2] ; } return dp[n]; } };
