在状态之间反复横跳

一、 前言：什么是状态机模型？

💬 开篇：之前的题目（比如斐波那契、路径），我们的状态通常只有一个维度变化（比如走到第 i 步）。

🚀 核心升级：但在股票交易中，第 i 天结束时，你可能处于完全不同的状态：

• 手里有股票（Hold）
• 手里没股票（Cash）
• 刚卖完处于冷冻期（Cooldown）

所有的决策（买入、卖出、休息），本质上都是在这些状态之间流转。搞懂了状态转移图，代码就是照着图“抄”下来而已！

---

二、 股票买卖含冷冻期 (Medium)

2.1 题目描述

题目链接：309. 最佳买卖股票时机含冷冻期

描述：
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。求最大利润。

示例：
输入: [1,2,3,0,2]
输出: 3
解释: 买入 -> 卖出 -> (冷冻) -> 买入 -> 卖出

2.2 状态机图解

我们需要三个状态来描述第 i 天的情况：

1. 买入状态 (dp[i][0])：手里有股票。

   • 来源：可能是昨天就有，也可能是今天刚买的。

2. 可交易状态 (dp[i][1])：手里无股票，且不在冷冻期。

   • 来源：可能是昨天就没股票，也可能是昨天刚过完冷冻期。

3. 冷冻状态 (dp[i][2])：手里无股票，且处于冷冻期（因为今天刚刚卖了）。

   • 来源：必然是昨天手里有股票，今天卖了。

2.3 状态转移方程

1. dp[i][0] (有股票)

   • 昨天就有 (dp[i-1][0])
   • 昨天是可交易状态，今天买了 (dp[i-1][1] - prices[i])
   • dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

2. dp[i][1] (可交易/无股票)

   • 昨天就是可交易状态 (dp[i-1][1])
   • 昨天是冷冻期，今天解冻了 (dp[i-1][2])
   • dp[i][1] = max(dp[i-1][1], dp[i-1][2])

3. dp[i][2] (冷冻期/刚卖出)

   • 昨天有股票，今天卖了 (dp[i-1][0] + prices[i])
   • dp[i][2] = dp[i-1][0] + prices[i]

2.4 代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // dp[i][0]: 手里有股票
        // dp[i][1]: 手里无股票，且不在冷冻期（可买入）
        // dp[i][2]: 手里无股票，且在冷冻期（刚卖出）
        vector<vector<int>> dp(n, vector<int>(3));

        // 初始化
        dp[0][0] = -prices[0]; // 第一天买入
        dp[0][1] = 0;          // 第一天啥也不干
        dp[0][2] = 0;          // 第一天不可能处于冷冻期（假设为0即可）

        for (int i = 1; i < n; i++) {
            // 1. 有股票：延续昨天有，或者今天买（从可交易状态买）
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            
            // 2. 可交易：延续昨天可交易，或者从冷冻期恢复
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            
            // 3. 冷冻期：必然是昨天有股票，今天卖了
            dp[i][2] = dp[i - 1][0] + prices[i];
        }

        // 最后手里没股票的两种情况取最大
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

---

三、 股票买卖含手续费 (Medium)

3.1 题目描述

题目链接：714. 买卖股票的最佳时机含手续费

描述：
可以无限次交易，但每笔交易（买入+卖出）要付一笔手续费 fee。

示例：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8

3.2 简化状态

这题没有冷冻期，所以状态很简单，只有两个：

1. f[i] (Hold)：手里有股票。
2. g[i] (Cash)：手里无股票。

3.3 状态转移方程

手续费什么时候扣？
为了方便，我们统一在卖出的时候扣除 fee。

1. f[i] (持有)

   • 昨天就持有：f[i-1]
   • 昨天没持有，今天买：g[i-1] - prices[i]
   • f[i] = max(f[i-1], g[i-1] - prices[i])

2. g[i] (空仓)

   • 昨天就空仓：g[i-1]
   • 昨天持有，今天卖（记得扣手续费）：f[i-1] + prices[i] - fee
   • g[i] = max(g[i-1], f[i-1] + prices[i] - fee)

3.4 代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        
        vector<int> f(n); // 持有
        vector<int> g(n); // 空仓
        
        // 初始化
        f[0] = -prices[0]; // 第一天买入
        g[0] = 0;          // 第一天没动
        
        for(int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        
        return g[n - 1];
    }
};

---

四、 买卖股票 III (Hard) - 最多 2 笔

4.1 题目描述

题目链接：123. 买卖股票的最佳时机 III

描述：
最多可以完成 两笔 交易。

示例：
输入：[3,3,5,0,0,3,1,4]
输出：6

4.2 升维：为什么需要新维度？

之前我们不限制交易次数，所以不需要记录“这是第几次买卖”。现在有了限制，我们就必须要把交易次数写进状态里。

状态定义：
dp[i][k][0]：第 i 天，完成了 k 次交易，处于买入（持有）状态。
dp[i][k][1]：第 i 天，完成了 k 次交易，处于卖出（空仓）状态。

对于本题，最多 2 次，其实我们可以把状态拆解得更直观一点，直接列举所有可能：

1. Buy1：第一次买入
2. Sell1：第一次卖出
3. Buy2：第二次买入
4. Sell2：第二次卖出

4.3 状态转移方程

• Buy1[i]：延续昨天 Buy1，或者今天刚开始买（-prices[i]）
• Sell1[i]：延续昨天 Sell1，或者今天把 Buy1 卖了（+prices[i]）
• Buy2[i]：延续昨天 Buy2，或者今天用 Sell1 的钱接着买（+Sell1 - prices[i]）
• Sell2[i]：延续昨天 Sell2，或者今天把 Buy2 卖了（+prices[i]）

4.4 代码实现（通用化写法）

为了对接下一题（k 次交易），我们这里使用二维数组写法，k 代表交易次数。
我们定义 j 为正在进行第 j 笔交易。

class Solution {
public:
    const int INF = 0x3f3f3f3f;

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // f[i][j]: 第 i 天，交易了 j 次，处于【买入/持有】状态
        // g[i][j]: 第 i 天，交易了 j 次，处于【卖出/空仓】状态
        // 这里的 j 我们定义为：已经完成的交易次数 
        // 最多 2 次交易，所以 j 最大是 2
        // 为了方便，我们将 j 理解为 "第 j 次交易过程"
        vector<vector<int>> f(n, vector<int>(3, -INF));
        vector<vector<int>> g(n, vector<int>(3, -INF));

        // 初始化
        f[0][0] = -prices[0]; // 第 0 天，第 1 次交易买入
        g[0][0] = 0;          // 第 0 天，还没开始，收益 0

        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                // f[i][j] (持有): 
                // 1. 昨天就持有 f[i-1][j]
                // 2. 昨天空仓，今天买入 g[i-1][j] - price
                f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);

                // g[i][j] (空仓):
                // 1. 昨天就空仓 g[i-1][j]
                // 2. 昨天持有(上一轮 j-1)，今天卖出 f[i-1][j-1] + price
                // 注意：这里定义略有不同，如果我们认为卖出才算完成一次交易
                // 那么卖出时的状态转移应该来自 f[i-1][j-1]
                
                g[i][j] = g[i-1][j];
                if(j >= 1) { // 必须有上一次的买入才能卖出
                     g[i][j] = max(g[i][j], f[i-1][j-1] + prices[i]);
                }
            }
        }

        // 找到最后一天，完成 0, 1, 2 次交易中的最大值
        int ret = 0;
        for(int j = 0; j < 3; j++) ret = max(ret, g[n-1][j]);
        return ret;
    }
};

(注：上面的代码逻辑中，g 和 f 的下标 j 的对应关系需要非常小心。这里采用的是题目中给出的通用模板逻辑：f[i][j] 表示第 j 次交易买入，g[i][j] 表示第 j 次交易卖出完成)

---

五、 买卖股票 IV (Hard) - 最多 k 笔

5.1 题目描述

题目链接：188. 买卖股票的最佳时机 IV

描述：
最多可以完成 k 笔交易。

示例：
输入：k = 2, prices = [2,4,1]
输出：2

5.2 核心思路：把 2 变成 k

这题就是上一题的泛化版。
我们只需要把上一题代码里的 3 改成 k+1 即可。

细节优化：
如果 k 非常大（超过天数的一半 n/2），那其实就等于无限次交易（这不就是题目 II 吗？）。为了防止申请超大数组导致内存溢出，可以做个特判：k = min(k, n / 2)。

5.3 状态转移逻辑图

5.4 代码实现

class Solution {
public:
    const int INF = 0x3f3f3f3f;

    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        // 优化：交易次数不可能超过天数的一半
        k = min(k, n / 2);

        // f[i][j]: 第 i 天，已进行 j 次交易，【持有】股票
        // g[i][j]: 第 i 天，已完成 j 次交易，【不持有】股票
        // 注意：j 从 0 到 k。
        // 这里定义：
        // f[i][j] 表示正在进行第 j+1 次交易（买入状态）
        // g[i][j] 表示已完成第 j 次交易（卖出状态）
        
        vector<vector<int>> f(n, vector<int>(k + 1, -INF));
        vector<vector<int>> g(n, vector<int>(k + 1, -INF));

        // 初始化
        f[0][0] = -prices[0]; // 第 0 天，开启第 1 笔交易
        g[0][0] = 0;          // 第 0 天，啥也不干，算完成 0 笔

        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= k; j++) {
                // 【持有状态】 f[i][j]
                // 1. 延续昨天持有
                // 2. 昨天是【完成 j 次交易】的状态，今天买入开启第 j+1 次
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);

                // 【空仓状态】 g[i][j]
                // 1. 延续昨天空仓
                // 2. 昨天是【正在进行 j 交易】(即f[i-1][j-1])，今天卖出
                // 注意：这里 j 需要 >= 1，因为卖出意味着完成了一次新的交易
                
                g[i][j] = g[i - 1][j]; // 默认延续
                if(j >= 1) {
                    // 完成第 j 次交易，意味着要把第 j 次买入的股票卖掉
                    // 对应的买入状态是 f[i-1][j-1]
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for(int j = 0; j <= k; j++) {
            ret = max(ret, g[n - 1][j]);
        }
        return ret;
    }
};

---

六、 总结：股票问题的通用模板

💬 总结：恭喜你，成为了股票交易大师！

我们把所有股票问题归纳为一个通用公式：

$$\{\begin{array}{l}Hold[i][k]=\max (Hold[i-1][k],Cash[i-1][k]-prices[i])Cash[i][k]=\max (Cash[i-1][k],Hold[i-1][k-1]+prices[i])\end{array}$$

• 121 (只买一次)：k=1，Cash[i-1][k] 也就是 0。
• 122 (无限次)：k 无穷大，k-1 和 k 没区别，退化为二维。
• 309 (冷冻期)：Buy 依赖于 Cooldown（前天卖出）。
• 714 (手续费)：卖出时减去 fee。
• 123/188 (k次)：严格遵守上面的公式，循环 k 即可。