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

123. Best Time to Buy and Sell Stock III

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

其实和背包问题很类似，背包问题是 物品装与不装，股票就是买与不买。不同点在于，股票在买与不买的基础上，还有卖与不卖的另一种状态！

无操作=当日买入+当日再卖出
代码随想录中dp包含5种状态，他是4种状态+1种操作（无操作）。
我这里给出和之前121题、122题背包问题，一致的解析，即dp存储的是股票持有的状态，一共4种。
dp(4)

1. dp[0] 第一次持有股票
2. dp[1] 第一次不持有
3. dp[2] 第二次持有股票
4. dp[3] 第二次不持有

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];
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

其实还有一个问题要清楚，买与卖的操作，持有不持有的状态，只是便于我们理解，dp也可以表示为操作，
0.无操作 1.第一次买入 2.第一次卖出 3.第二次买入 4.第二次卖出。

哪种方式能让你容易理解，你就用哪种去理解，最后公式结果都是一样的。

优化版

因为我们只是用两行数据第 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();
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意事项：

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]也无影响。

188. Best Time to Buy and Sell Stock IV

k次交易，dp包含2 * k个状态，

1. 第1次持有
2. 第1次不持有
3. 第2次持有
4. 第2次不持有
5. 。。。。。。。。

注意：第i天第1次持有是dp[i][1]=-prices[i] ，而其他第2、3、4…次持有都是带历史收益的dp[i][1]=dp[i-1][1] - prices[i]
为了使代码保持一致，多出第0次状态。dp[i][0]=0，。
dp[i][1]=dp[i-1][1] - prices[i]

/**
 * @Date: 2023 Dec 27
 * @Time: 22:17
 * @Author: Chris
 * @Title: 188. Best Time to Buy and Sell Stock IV
 * @Link:
 *https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
 **/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
 public:
  int maxProfit(int k, vector<int>& prices) {
    vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
    // j奇数为买入，减去第一天股票价格
    for (int j = 1; j < 2 * k + 1; j += 2) {
      dp[0][j] = -prices[0];
    }
    // j = 0. 无操作，值为0，便于统一第一次买入操作
    //   = 1. 第一次持有
    //   = 2. 第一次不持有
    //   = 3. 第二次持有
    //   = 4. 第二次不持有
    //   = 5................
    // 从第二天开始
    for (int i = 1; i < prices.size(); ++i) {
      // 从j=1开始 一次计算2个状态，比如1,2; 3,4; 5,6;
      for (int j = 1; j < 2 * k; j += 2) {
        // 第i天持有 = i-1天不持有，今日买入 ｜ 与i-1天的持有状态保持一致
        dp[i][j] = max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
        // 第i天不持有 = i-1持有，今日卖出 ｜ 与i-1天的不持有状态保持一致
        dp[i][j + 1] = max(dp[i - 1][j] + prices[i], dp[i - 1][j + 1]);
      }
    }
    return dp.back().back();
  }
};

int main() { return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41