4. 爬楼梯（改写成完全背包）
题目
原题为LeetCode-70，是一道简单动态规划，现改写为：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 m mm 个台阶。你有多少种不同的方法可以爬到楼顶呢
思路
一步爬一个或两个或三个或 m mm 个就是物品，楼顶就是背包，其实就是问装满背包的方法有多少种。再想这是排序数还是组合数？明显先2后1（先爬2阶楼梯再爬1阶楼梯）和先1后2是不同的方法，所以求的是排序数，那么就要求先遍历背包，嵌套遍历物品
五部曲
dp[j] 含义
爬到有 j 个台阶的楼顶的方法数
递推公式
d p [ j ] + = d p [ j − i ]
数组初始化
dp[0]=1
遍历顺序
上文已说明
代码实现
class Solution { public: int climbStairs(int n, int m) { vector<int> dp(n + 1, 0); dp[0] = 1; for (int i = 1; i <= n; i++) { // 遍历背包 for (int j = 1; j <= m; j++) { // 遍历物品 if (i - j >= 0) dp[i] += dp[i - j]; } } return dp[n]; } };
代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了
