LeetCode 70 爬楼梯

70.爬楼梯

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

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

动态规划

1. 动态规划数组的下标及含义： dp[i] 表示总计 i 个楼梯的爬楼方式，总计的长度为n

2. 递推公式： dp[i]=dp[i-1]+dp[i-2] ，此处的理解可以使当前剩余 i 阶楼梯，当前这一步分别走一步或者两步。

3. dp数组的初始化：当 i=1 时，明显不存在方法 dp[1]=1 ，当 i=2 时，只能走一步 dp[2]=2

4. 遍历顺序：此处需要求解的是 dp[n] 那么明显需要从前向后进行递推

5. 举例推导：n=3 dp[3]=dp[1]+dp[2]=3 满足要求

此处在初始化时，有一个较为重要的细节，就是对于 dp[0] 的定义和初始化，从 dp 数组的定义来看，此处的 dp[0] 应该代表的是，总计0个阶梯有几种爬法，那么应该是不存在爬得方式，应该是初始化为0，但是如果使用 dp[0],dp[1] 去计算 dp[2] 将会得到错误的结果，因此此处不应该初始化 dp[0] 将 dp[1],dp[2] 作为初始值去计算。

根据此处的递推公式：当前状态 i 的决策，也只和前两个状态有关，那么只需要保存前两个状态的值，实现空间复杂度的化简。

class Solution {
public:
    int climbStairs(int n) {
        if(n<3) return n;
        int dp[2];
        dp[0]=1,dp[1]=2;
        int res;
        for(int i=3;i<=n;i++){
            res=dp[0]+dp[1];
            dp[0]=dp[1];
            dp[1]=res;
        }
        return res;
    }
};

使用完全背包问题求解

将问题进行转化：物品数组总共包含两个元素 1，2 ，使用物品装满容量为 n 的背包。并且此处是一个排列问题，因为 1,2 和 2,1 是两种不同的爬楼梯方式。那么此处就一定需要先遍历背包，再遍历物品。

1. 动态规划数组的定义：定义数组 dp[n+1] 表示爬到楼梯 n 的方案数

2. 动态规划数组的推导：在第 j 迭代中，表示爬到楼梯 j 拥有的方案数，那么可以从 j-1 到达也可以从 j-2 到达。那么 dp[j]=j>=nums[i]?dp[j]+dp[j-nums[i]]:dp[j]

3. 动态规划数组的初始化：对于 dp[0] 只有一种方案到达。那么 dp[0]=1

4. 动态规划数组dee遍历顺序：先遍历背包，再遍历物品，都是从前向后遍历。

5. 举例验证：对于 n=2 ，那么 dp[2]=dp[1]+dp[0]=2 验证成立

代码实现：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1,dp[1]=1; // 这样的初始化方式实现问题的简化，避免从1开始-2，出现问题
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

将上述问题转变为楼梯的选择可以是 1-m 种，也就是每次走楼梯的选择可以是 1-m 步的任意一种。那么此处动态规划数组的定义和遍历方式依旧不变，但是递推方式改为： dp[j]=j>=i?dp[j]+dp[j-i]:dp[j] ，那么总体的代码实现为：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1; // 此处只需要初始一个
        for(int j=2;j<=n;j++){
            for(int i=1;i<=m;i++){
                dp[j]=j>=i?dp[j]+dp[j-i]:dp[j];
            }
        }
        return dp[n];
    }
};