代码随想录算法训练营（动态规划10，11 股票问题）| 121. 买卖股票的最佳时机 & 122.买卖股票的最佳时机II

动态规划10

动态规划5步曲，个人感觉应该加一步状态分析

状态分析：

1. 列出所有的状态，将状态归纳后定义dp数组
2. 状态转移，状态怎么转移也就是递推公式是什么

买卖股票的动规五部曲分析如下：

1 确定dp数组（dp table）以及下标的含义

列出所有的状态：

1. 持有 持有状态包含两种情况，继续持有和当天买入
2. 不持有 不持有包含两种状态，当天卖出和维持前一天的未持有状态

dp[i][0] 表示当天持有或者当天买入的的最大值
dp[i][1] 表示当天不持有的最大值

确定递推公式

继续持有就是 dp[i-1][0] 上一天的持有的值
当天买入就是前一天的没有买入的值减去当天股票的价值
可以得出，当天持有
dp[i][0] = max(dp[i - 1][0], -prices[i]);

dp[i][1] 表示当天不持有的最大值
就是保持前一天的未持有状态和当天卖出的状态的最大值
dp[i][1] = max(dp[i - 1][1], + prices[i]);

dp数组如何初始化

由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

其基础都是要从dp[0][0]和dp[0][1]推导出来。

那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;

最大值一定是最后一次卖出的价格

121. 买卖股票的最佳时机

leetcode题目链接
视频讲解
文章讲解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(2,0));
        //dp[i][0] 表示当天持有的最大价值
        //dp[i][1] 表示当天卖出后不持有的最大价值
        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int i = 1; i < prices.size(); i ++) {
            dp[i][0] = max(dp[i-1][0], 0 - prices[i]);
            //dp[i][0] = max(dp[i-1][0], dp[i-1][1] -prices[i]);
            //当天卖出一定是在前面买入的情况下卖出的，所以是dp[i-1][0] + prices[i]
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        //最大值一定是最后一次卖出的价格
        return dp[prices.size() -1][1];
    }
};

122.买卖股票的最佳时机II

leetcode题目链接
视频讲解
文章讲解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < prices.size(); i ++) {
            // 买入必须是卖出之后才能买入
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
            //卖出必须是买入之后才能卖出
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[prices.size()-1][1];
    }
};

动态规划11

一天可以买卖多次很重要

123.买卖股票的最佳时机III

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
leetcode题目链接
视频讲解
文章讲解

// 版本一
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.size() - 1][4];
    }
};

188.买卖股票的最佳时机IV

本题是123.买卖股票的最佳时机III 的进阶版
leetcode题目链接
视频讲解
文章讲解

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {

        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
        for (int j = 1; j < 2 * k; j += 2) {
            dp[0][j] = -prices[0];
        }
        for (int i = 1;i < prices.size(); i++) {
            for (int j = 0; j < 2 * k - 1; j += 2) {
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[prices.size() - 1][2 * k];
    }
};