代码随想录算法训练营第三十八天| ● 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

理论基础 

代码随想录 (programmercarl.com)

动态规划的五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

斐波那契数 

题目链接：509. 斐波那契数 - 力扣（LeetCode）

思路：还好。

class Solution {
public:
    int fib(int n) {
        vector<int> v;
        v.push_back(0);v.push_back(1);
        if(n==0)return 0;
        for(int i=1;i<n;i++){
            v.push_back(v[i]+v[i-1]);
        }
        return v.back();
    }
};

但是不必要维护整个序列，只需要几个变量即可

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

爬楼梯 

题目链接：70. 爬楼梯 - 力扣（LeetCode）

思路：dp[i]的含义就是到第i层有几种跳法，只有这一点，其他没什么了。

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

使用最小花费爬楼梯 

题目链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）

思路：dp[i]的含义是从第i层离开需要花费多少。答案必然从倒数第一层或倒数第二层之间获得，因此返回值是二者之中的最小值。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp;
        dp.push_back(cost[0]);
        dp.push_back(cost[1]);
        for(int i=2;i<cost.size();i++){
            dp.push_back(cost[i]+min(dp[i-1],dp[i-2]));
        }
        return min(dp[dp.size()-1],dp[dp.size()-2]);
    }
};

同样也不需要维护整个vector,而且dp也可以视为到达第i层需要的花费，

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
            dp0 = dp1; // 记录一下前两位
            dp1 = dpi;
        }
        return dp1;
    }
};