70. 爬楼梯进阶版

参照于代码随想录
70. 爬楼梯

此题将原题进行了部分修改：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个…n个台阶。你有多少种不同的方法可以爬到楼顶呢？

dp数组含义:
dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。

递推公式：
dp[i] += dp[i -j];

初始化：
dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。

遍历顺序：
这是一个完全背包，所以是顺序遍历，通过分析可知这个dp中的序列是排列，所以要注意两个for循环嵌套的顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包
如果求排列数就是外层for遍历背包，内层for循环遍历物品
把题目进行转换：
一步一个台阶两个台阶等等，然后整个过程就是，每次走多少个台阶然后到楼顶。
可以这样想：可以走的台阶数为一个数组，从数组里面取值（每个元素可重复取）其和为上到楼顶所需要的台阶数。
这时就可以很清楚的知道这是一个完全背包问题。

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) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

代码中m表示可以爬1~m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了。