代码随想录day50:动态规划｜买卖股票的最佳时机III&IV

123. Best Time to Buy and Sell Stock III

股票问题就是分清有几个状态，然后弄清每个状态是由哪个状态转化而来的。

无操作=当日买入+当日再卖出

dp[i][0]= max(dp[i - 1][0], -prices[i]); // 注意第一次买入，不能加历史记录！

/**
 * @Date: 2023 Dec 27
 * @Time: 08:08
 * @Author: Chris
 * @Title: 123. Best Time to Buy and Sell Stock III
 * @Link:
 *https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
 **/
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
  // at most two transactions
  // mush sell the stock before buy again
 public:
  //  状态分析：
  //          0. 第一次持有股票
  //          1. 第一次不持有
  //          2. 第二次持有股票
  //          3. 第二次不持有
  int maxProfit(vector<int>& prices) {
    vector<vector<int>> dp(prices.size(), vector<int>(4));
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = -prices[0];
    dp[0][3] = 0;
    for (int i = 1; i < prices.size(); ++i) {
      // 第一次持有 = 第一次保持持有｜ i-1不持有 今日买入。
      // 注意第一次买入，不能加历史记录！和121题一致
      dp[i][0] = max(dp[i - 1][0], -prices[i]);
      // 第一次不持有= 第一次保持不持有｜ i-1持有，今日卖出
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
      // 第二次持有 = 第二次保持持有｜ i-1第一次不持有，今日买入
      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]);
    }
    return dp.back()[3];
  }
};

优化版

因为我们只是用两行数据第 i 行和 i-1 行，所以可以用2行的滚动数组存储，2行还可以压缩为1行。为什么？ 因为for循环（假设从前向后遍历）每个元素，更新一个元素时，其后面的元素就是上一行的历史数据。从后向前遍历，同理。

class Solution {
 public:
  // 滚动数组空间优化
  int maxProfit(vector<int>& prices) {
    //  状态分析：
    //          0. 第一次持有股票
    //          1. 第一次不持有
    //          2. 第二次持有股票
    //          3. 第二次不持有
    vector<int> dp(4, 0);
    dp[0] = -prices[0];
    dp[2] = -prices[0];
    for (int i = 1; i < prices.size(); ++i) {
      // dp[0]是求负数的最大值=求正数最小值，其实就是当前序列中最便宜的股票
      dp[0] = max(-prices[i], dp[0]);
      dp[1] = max(dp[0] + prices[i], dp[1]);
      dp[2] = max(dp[1] - prices[i], dp[2]);
      dp[3] = max(dp[2] + prices[i], dp[3]);
    }
    return dp.back();
  }
};

注意事项：

dp[0] = max(-prices[i], dp[0]);

dp[1] = max(dp[0] + prices[i], dp[1]);

看第二行代码，左侧dp[1]是当前第i天的第一次不持有状态， max函数中最右侧dp[1]是历史数据，dp[0] 而是第 i 天的最新的数据，因为dp[0]在第一行代码中先更新了。

为什么用当天最新的数据也可以？

那要明白dp[0]中存储的是什么？
dp[0] = max(-prices[i], dp[0]);

可以看出是股票历史最低价，不过是负数存储。

历史dp[0]存储的是 从第1天到第i-1天 股票最低价格，当日dp[0] 就多考虑了1天。

那么我们分析多考虑一天会不会对我们dp[1]数据造成影响？

因为dp[0]存储的是历史最低价，

所以看第i天是不是历史最低价？
? ? a.是→分析影响，
? ? b.不是→没影响不用管。因为不是的话，dp值没更新，当日dp[0] = 历史dp[0]，

是的话,收益为0。

dp[0] = -prices[i]; dp[0] + prices[i] == 0,

对dp[1]第一次卖出没影响的，因为第一次卖出dp[1]的全局最小值就是0，即当天买当天卖，其他时候我们所执行的操作都收益大于0的。

综上，分析思路：先找到区别点在哪里？再弄清区别具体是什么？
如果num[i]是历史最低,第一次持有dp[0]才会更新，但dp[0]+price[i]==0, 对dp[1]第一次卖出求最大值无影响。

同理 dp[1]没影响的话，dp[2]也就无影响，dp[3]也无影响。