DAY18-动态规划(一)

力扣网站的说明
动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。
动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。
使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

步骤可以整理成这样
基础状态->写出转移方程（对状态做推演）->变数的范围&关系->程序码

例题实战

用一个最简单的题目来应证步骤
70. 爬楼梯
1.基础状态
n = 1时答案是1
n = 2时答案是2
2.写出转移方程
经由题目可以发现每次只能上1or2阶，所以第i阶的方法数(dp[i])为dp[i-1]+dp[i-2]
dp[i] = dp[i-1]+dp[i-2]
3.变数的范围
发现dp[i]需要dp[i-1]&dp[i-2]所以i需要由3~n

class Solution {
public:
    int climbStairs(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        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];
    }
    //  递回法，超时
    // int climbStairs(int n) {
    //     if(n==1)
    //         return 1;
    //     if(n==2)
    //         return 2;
    //     return climbStairs(n-1)+climbStairs(n-2);
    // }
};

198. 打家劫舍
推演dp[i] = max(dp[i-1], dp[i-2]+nums[i])就结束了

class Solution {
public:

    //dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    int rob(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
        {
            return nums[0];
        }
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < dp.size(); i++){
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[dp.size()-1];
    }
};

121. 买卖股票的最佳时机
经典动态规划问题，直接看程序码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //遍历做法
        /*int Max = 0;
        for(int i = 0; i < prices.size(); i++)
        {
            for(int j = i; j < prices.size(); j++)
            {
                if(prices[j] - prices[i] > Max)
                {
                    Max = prices[j] - prices[i];
                }
            }
        }
        return Max;*/


        //DP思想  Max(上一个获利组合, 现在卖出-最低价钱)
        /*if (prices.size()==0)
            return 0;
        int Max = 0, Min = prices[0];
        for(int i = 0; i<prices.size(); i++){
            Max = max(Max, prices[i]-Min);
            Min = min(Min, prices[i]);
        }
        return Max;*/

        //贪心想法
        int Max = 0;
        for(int i = 0, j = 0; j<prices.size(); j++){
            if(prices[j]-prices[i]>0){
                Max = max(Max, prices[j]-prices[i]);
            }
            else
                i = j;
        }
        return Max;
    }
};

补充一下贪心思路：
假设在第i天买入，今天是第j天＆prices[j]>prices[i]，能赚的价差就是prices[j]-prices[i]
若prices[j] < prices[i]，那就更新买入的时间点（i)，就可以保证最佳解