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

考点

• 状态机DP
• 滚动数组

1. 状态定义

设 \[ f[k][i][s] \] 表示在处理完前 \(i\) 天之后：

• 已经进行了 \(k\) 次操作（一次买入或卖出均算一次操作）
• 当前持股状态为 \(s\in\{0,1\}\)
  • \(s=0\)：不持股
  • \(s=1\)：持股

所得的最大收益。

最多允许 \(4\) 次操作，对应两笔完整交易： 买(1)、卖(2)、买(3)、卖(4)。

---

2. 初始状态

天数为 \(0\) 时，无论允许的操作次数是多少：

1. 不持股状态： \[ f[k][0][0] = 0 \] 因为尚未开始交易，收益必为零。

2. 持股状态： \[ f[k][0][1] = -\infty \] 表示在未开始交易前不可能持股，因此为不可达状态。代码中使用一个足够小的数 neg 近似 \(-\infty\)。

---

3. 状态转移方程

设第 \(i\) 天价格为 \(\text{price}_i\)。

转移在本质上依赖两个来源：

• 本阶段上一列： \(f[k][i-1][\cdot]\)
• 上一阶段上一列： \(f[k-1][i-1][\cdot]\)

这构成一个二维网格上“向左”和“左上角”的传递结构。

3.1 不持股状态 \(f[k][i][0]\)

\[ f[k][i][0] = \max\left( f[k][i-1][0],\quad f[k-1][i-1][1] + \text{price}_i \right) \]

解释：

• 若第 \(i\) 天不操作，则继承前一天不持股状态。
• 若第 \(i\) 天卖出，则必须来自上一阶段的持股状态 \(f[k-1][i-1][1]\)，卖出得到 \(\text{price}_i\)。

3.2 持股状态 \(f[k][i][1]\)

\[ f[k][i][1] = \max\left( f[k][i-1][1],\quad f[k-1][i-1][0] - \text{price}_i \right) \]

解释：

• 若第 \(i\) 天不操作，则继续持股。
• 若第 \(i\) 天买入，则来自上一阶段的不持股状态 \(f[k-1][i-1][0]\)，买入消耗 \(\text{price}_i\)。

---

4. 关于“买了再卖”等无收益操作

在该模型中，每次买或卖都会消耗一次操作次数，因此：

• 一个“买+卖”组合将消耗两次操作。
• 若该组合没有带来收益（如价格不涨），则整体不会提升收益，反而浪费宝贵的操作次数。

因此 DP 中不会主动选择这类无效操作路径，除非该路径意外产生高收益。这也是为什么 DP 会自然排除“买了立刻卖但无收益”这种无意义行为。

---

5. 最终答案

由于最多允许 4 次操作，最终必须返回： \[ \text{Ans} = f[4][n][0] \] 即第 \(n\) 天结束时，完成最多两笔完整交易（共 4 次操作），并且不持股时的最大收益。

6. 代码

class Solution {
public:
    static const int maxn = 1e5 + 5, neg = 0xcfcfcfcf;
    int maxProfit(vector<int>& prices) {
        int f[5][maxn][2], n = prices.size();
        for (int i = 0; i < 5; ++i)
            f[i][0][0] = 0, f[i][0][1] = neg;
        for (int k = 1; k < 5; ++k) {
            for (int i = 1; i <= n; ++i) {
                f[k][i][0] =
                    max(f[k][i - 1][0], f[k - 1][i - 1][1] + prices[i - 1]);
                f[k][i][1] =
                    max(f[k][i - 1][1], f[k - 1][i - 1][0] - prices[i - 1]);
            }
        }
        return f[4][n][0];
    }
};

当然可以进行滚动数组，可以发现，之前我们是以k作为阶段的

即f[k-1][i-1]的0/1与f[k][i-1]的0/1去更新f[k][i]的0/1

i-1 i
A   B  k-1
C   D  k

但这样并不符合滚动数组的要求，因为滚动数组本质就是只用到上一次的状态

那么我们横着看，把i作为阶段就一目了然了，

即f[i-1][k-1]和f[i-1][k]的0/1去更新f[i][k]的0/1

逻辑上与上一份代码一模一样，但是就可以满足滚动数组的要求：

class Solution {
public:
    static const int maxn = 1e5 + 5, neg = 0xcfcfcfcf;
    int maxProfit(vector<int>& prices) {
        int f[5][2], n = prices.size();
        for (int i = 0; i < 5; ++i)
            f[i][0] = 0, f[i][1] = neg;
        for (int i = 1; i <= n; ++i) {
            for (int k = 4; k >= 1;--k) {
                f[k][0] =
                    max(f[k][0], f[k - 1][1] + prices[i - 1]);
                f[k][1] =
                    max(f[k][1], f[k - 1][0] - prices[i - 1]);
            }
        }
        return f[4][0];
    }
};