day 38 动态规划（1）

day38
代码随想录
2024.1.6
开始动态规划！
递归五部曲：

1. 确定dp数组含义
2. 确定递推公式
3. dp数组初始化
4. 遍历顺序
5. 举例推导dp数组

1. 50斐波那契数列
经典的动态规划入门第一题，直接递归五部曲，

1. 本题递归数组是具体要求的值，而dp数组下标则是所给参数n
2. 根据题目要求，递推公式应该为，从第三个数开始，每个数等于前两个数之和
3. dp初始化本题题目已给
4. 根据递归公式，遍历顺序为从左往右
5. n=0，n=1，然后n=2值为前两个之和为1，以此类推。

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

2. 70爬楼梯

1. 首先，本题dp数组含义是有多少种爬楼梯的方法，而下标n表示楼梯阶数
2. 这道题递推公式得稍微思考一下，首先针对一个阶梯为n得，最后一步是能走一步或两步，走一步时前一步就是n-1层，走两步前一层就是n-2层，因为，阶梯为n的无非就两种情况，加起来就好，会发现，跟斐波那契数列递推公式相同
3. 本题不存在n=0，n=1和n=2就是初始化值
4. 同理，从左往右
5. 类比斐波那契数

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2) return n;
        vector<int> dp(n+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];
    }
};

3. 746使用最小代价爬楼梯
这道题初始化开始没有弄清楚

1. dp数组为最小花费，i是楼梯数
2. 与爬楼梯类似，i楼梯是i-1和i-2楼梯而来，不过，此时不是相加，因为要求最小花费，而dp[i-1]是到达该层的花销，要加上之后的开销cost[i-1]，i-2也是一样，然后在这两种情况中找最小值
3. 这是开始没弄清的情况，0和1开始的不用花费因此都是0
4. 当然还是从左往右
5. 略！

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        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()];
    }
};