Shouyu

Appearance

买卖股票的最佳时机III ​

题目描述 ​

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

C++
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

文章讲解：https://programmercarl.com/0123.买卖股票的最佳时机III.html

思路 ​

121. 买卖股票的最佳时机 (opens new window) 是单次买卖， 122.买卖股票的最佳时机II (opens new window)是无限次买卖。

本题是最多买卖两次，对买卖次数做了限制。

我们依然使用五部曲来分析

动规五部曲 ​

1、dp数组及下标含义 ​

每天的状态不再是持有和不持有两个状态。而是可以划分为5个状态。

这5种状态分别定义了处于交易的哪个阶段。

  1. dp[i][0] 第i天时 还没有开始交易 dp[i][0] 沿用前一天状态
  2. dp[i][1] 第i天时 第一次交易持有，可能是当天买的，也可能是前一天就已经买了 dp[i][1] = dp[i - 1][0] - prices[i], dp[i - 1][1]
  3. dp[i][2] 第i天时第一次交易没持有，可能是这天卖出了，或者是前一天就已经卖出了 dp[i][2] = dp[i -1][1] + prices[i] , dp[i - 1][2]
  4. dp[i][3] 第i天时第二次交易持有，可能是这天买入的或者是前一天就已经买入了
  5. dp[i][4] 第i天时第二次交易没持有，可能是这天卖出了，或者是前一天就已经卖出了

dp[i][j]中 i 表示第 i 天，j 为 [0 - 4] 五个状态，dp[i][j]表示第 i 天状态 j 所剩最大现金。

2、递推公式 ​
C++
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]);
3、dp数组初始化 ​

把第0天的状态都定义出来。

第0天没有开始交易，dp[0][0] = 0;

第0天第一次买入，dp[0][1] = 0-prices[0];

第0天第一次卖出，？？第一天我还没买怎么卖出？其实本题并没有规定不能当天买当天卖，不像 121. 买卖股票的最佳时机 (opens new window) 那样做出了限制（实际上那不算做限制，只是为了声明只允许买卖一次）。因此可以理解为当天买当天卖，多以 dp[0][2] = 0;

第0天第二次买入，同上，当天买了、卖了，又买了，dp[0][3] = 0 - pricrs[0];

第0天第二次卖入，同上，当天买了、卖了，又买了，又卖了 dp[0][4] = 0;

4、确定遍历顺序 ​

从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

5、举例推导 ​

[1,2,3,4,5]为例

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

代码实现 ​

C++
int maxProfit(vector<int> &prices) {
    if (prices.empty()) return 0;
    // dp[i][0]: 未开始交易（始终为0）
    // dp[i][1]: 第一次持有
    // dp[i][2]: 第一次不持有（已卖出一次）
    // dp[i][3]: 第二次持有
    // dp[i][4]: 第二次不持有（完成两次交易）
    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 < (int)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.back()[4];
}