代码随想录算法训练营第38天 [ 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯]

代码随想录算法训练营第38天 [ 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯]

动态规划做题顺序

1.明确dp数组的含义
2.递推公式
3.dp数组的初始化
4.确认遍历的顺序
5.举例看看递推公式满不满足

一、509. 斐波那契数

链接: 代码随想录.
思路：经典dp数组
做题状态：看解析后做出来了

class Solution {
public:
    int fib(int n) {
        if(n<=1){
            return n;
        }
        vector<int> arr(2);
        arr[0] = 0;
        arr[1] = 1;
        for(int i = 2;i<=n;i++){
            int tmp = arr[0] + arr[1];
            arr[0] = arr[1];
            arr[1] = tmp;
        }
        return arr[1];
    }
};

二、70. 爬楼梯

链接: 代码随想录.
思路：经典dp数组
做题状态：看解析后做出来了

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1);
        if(n<=1){
            return 1;
        }
        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. 使用最小花费爬楼梯

链接: 代码随想录.
思路：dp数组
做题状态：看解析后做出来了

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // dp[i] 是走到i的花费
        // 从i-1 走到 i
        // 走一步的 dp[i] = dp[i-1] + cost[i-1]
        // 走两步是dp[i]=dp[i-2]+ cost[i-2]
        // 第一次走不消耗，所以dp[0] == dp[1] == 0
        // 取最小值
        // 从前往后
        vector<int> dp(cost.size() + 1);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
};