leetcode

70.爬楼梯

力扣链接

动规五部曲

1. 确定用作状态转移的dp数组的下标及含义 到达i阶有dp[i]种方法
2. 动规核心 状态转移方程/递推公式 dp[i] = dp[i-1]+dp[i-2]
3. dp数组如何初始化 dp[1] = 1, dp[2] =2
4. 确定遍历顺序 从前向后遍历
5. 打印dp数组用于排错

动态规划—空间优化

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

动态规划

class Solution {
public:
    int climbStairs(int n) {
        if (n==1) return n; // n=1特殊情况直接返回 因为dp(1) dp[1]会越界
        std::vector<int> dp(n); // 爬到j阶有dp[j]种方法
        dp[0]=1, dp[1]=2;
        for (int j=2; j<n;j++) dp[j]=dp[j-1]+dp[j-2]; // 背包
        return dp[n-1];
    }
};

递归会超时

class Solution {
public:
    int climbStairs(int n) {
        if(n<3)return n;// n>=1
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

This site is open source. Improve this page.