完全背包问题拓展（爬楼梯）

基础版爬楼梯：70. 爬楼梯 - 力扣（LeetCode）

进阶版爬楼梯，在这里我就自己描述进阶版爬楼梯题目

题目如下：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 m 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题目思路，这个一看，哎，和70题有大不相同，我原本只需要1或者2步就可以爬了，这一下跳到m个，我该怎么去解开这个问题呢，其实呢，我们同学想一想，这个题目我们只要把能走的台阶数，放到一个数组里面，把它当作物品，楼梯的n个台阶当作背包，爬楼梯嘛，也就是说能够上楼梯的方法，三阶楼梯，我走1步再走2步，和我走2步再走1步，这个是两个不一样的方法，那么这个是不是又是一个排列问题了呢，我们要是这么来转换就好办了，肯定编写完全背包问题，先遍历背包，在遍历物品，然后就可以找到所有的方法能够爬到n阶楼梯了。

以下是用完全背包去解开LeetCode70题的

class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= 2; j++){if(i - j >= 0 && INT_MAX - dp[i - j] >= dp[i])dp[i] += dp[i - j];}}return dp[n];}
};

这个题目只是给了能走1阶或者2阶

以下代码是解开能够m阶的爬楼梯题目

class Solution {
public:int climbStairs(int n) {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 && INT_MAX - dp[i - j] >= dp[i])dp[i] += dp[i - j];}}return dp[n];}
};

是不是我们只需要把第二层for循环里面的j <= 2换成j <= m就好了呀！