买卖股票的最佳时机如何用动态规划求解？（LeetCode 121 及变体）

简化版

给每天的股价 prices，求交易的最大利润。最基础的版本（只能买卖一次，LeetCode 121）：一边遍历、一边记录「到今天为止的最低价」，用今天价格减最低价更新最大利润，O(n)/O(1)。更通用的思路是状态机 DP：每天处于「持股」或「不持股」两种状态之一，用两个变量递推它们的最大利润——这套框架能统一处理「多次交易、含冷冻期、含手续费、限 k 次」等一系列变体。

详细版

状态机 DP（以「只买卖一次」为例）：

int maxProfit(int[] prices) {
    int cash = 0;                    // 不持股时的最大利润
    int hold = Integer.MIN_VALUE;    // 持股时的最大利润（初始还没买，视为负无穷）
    for (int p : prices) {
        cash = Math.max(cash, hold + p); // 今天不持股：昨天就没持 / 今天卖出(hold+p)
        hold = Math.max(hold, -p);       // 今天持股：昨天就持 / 今天买入(成本 -p，只能买一次)
    }
    return cash;                     // 最后手里没股票，利润最大
}

两个状态：cash（今天结束时不持股的最大利润）、hold（今天结束时持股的最大利润）。
只交易一次：买入时利润是 -p（此前利润必须是 0，因为只允许一次买卖）。
可多次交易（LeetCode 122）：只需把买入改成 hold = max(hold, cash - p)——买入时可以带上之前若干次交易的累计利润 cash。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、问题：一次买卖的最大利润

买卖股票 I（LeetCode 121）：prices[i] 是第 i 天的价格，你只能买入一次、之后卖出一次（必须先买后卖），求最大利润；无利可图则为 0。例如 [7,1,5,3,6,4]，第 2 天买（1）、第 5 天卖（6），利润 5。

二、朴素思路：维护历史最低价

最直接的 O(n) 解法：既然要「先买后卖、利润最大」，那对每一天，假设今天卖出，最好的买入点就是今天之前的最低价。于是遍历时维护一个 minPrice（到目前为止的最低价），每天用 prices[i] - minPrice 更新答案：

int min = prices[0], profit = 0;
for (int p : prices) {
    min = Math.min(min, p);              // 更新历史最低买入价
    profit = Math.max(profit, p - min);  // 今天卖出的最大利润
}

简单直观，但它不容易推广到「多次交易、带手续费」等变体。要统一处理，得上状态机 DP。

三、状态机 DP：持股 / 不持股两种状态

把「每天能处于的状态」抽象出来，是这类题的通用钥匙。任意一天结束时，手里只有两种状态：

持股（hold）：手上有一支股票，记此状态下的最大利润；
不持股（cash）：手上没有股票，记此状态下的最大利润。

我们递推每天这两个状态的最优值，最后答案一定是不持股状态（手里握着股票不卖显然不是最大利润）。

四、转移方程与状态压缩

每天的两个状态从昨天的状态转移而来：

今天不持股 cash：要么昨天就不持股（cash 不变），要么昨天持股、今天卖掉（hold + p）：
```
cash = max(cash, hold + p)
```

今天持股 hold：要么昨天就持股（hold 不变），要么今天买入。买入的成本取决于允许交易几次：

只买卖一次：  hold = max(hold, -p)          // 买入前利润必须是 0
可多次买卖：  hold = max(hold, cash - p)     // 买入可带上之前累计利润

因为每天只依赖昨天的两个值，用两个变量滚动即可，空间 O(1)。「只一次」和「多次」的差别，就浓缩在买入那一行是 -p 还是 cash - p——这正是状态机框架的威力。

五、扩展：多次交易 / 冷冻期 / 手续费 / 限 k 次

同一套「持股 / 不持股」状态机，稍加改动就能解一整个系列：

可多次交易（122）：买入用 cash - p（如上）。
含冷冻期（309）：卖出后要隔一天才能买，需多加一个「冷冻」状态，或买入时用「前天」的 cash。
含手续费（714）：卖出时减手续费，cash = max(cash, hold + p - fee)。
最多 k 次交易（188）：再加一维「已用交易次数」，dp[k][持股/不持股]，枚举交易次数。

这些变体的共同点，就是围绕「持股 / 不持股」加状态、改转移，掌握基础状态机后都能推导出来，这也是它作为 DP 状态机模型代表题的价值。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：第 i 天结束时分别维护持股和不持股的最大现金；一次交易限制使持股态买入来源是 -price[i]。

转移过程是：hold=max(hold,-p)，cash=max(cash,hold_old+p)；也等价于维护历史最低价。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：[7,1,5,3,6,4] 最低价降到 1，卖在 6 得 5；不能用 7→1 的下降抵消利润。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：同日更新时要明确使用旧状态；多次交易、手续费、冷冻期、最多 k 次都会改变状态维度与转移来源。

核对项	本题答案
复杂度	一次交易 O(n) 时间、O(1) 空间
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：一次交易可以累加所有上涨段。 那是可交易多次的 LeetCode 122。
误区：利润为负时应返回最小亏损。 题目允许不交易，答案至少为 0。
误区：所有股票变体都只要两个状态。 限 k 次需加入交易次数，冷冻期需额外状态或延迟依赖。
追问：hold 为什么可由 -price 产生？ 一次买入前现金基准为 0，持股现金就是买入成本的相反数。
追问：最低价法与 DP 是否不同？ 最低价法是一次交易 DP 的状态化简。
追问：如何处理手续费？ 通常在买入或卖出一侧扣一次，不能两边重复扣。

九、加强记忆

买卖股票用状态机 DP：每天处于持股 hold 或不持股 cash 两态，递推——cash=max(cash, hold+p)（保持 / 卖出）、hold=max(hold, 买入)。买入项是分水岭：只一次交易用 -p，可多次用 cash-p。答案取最后的 cash，两变量滚动 O(1) 空间。基础版也可「维护历史最低价、每天试卖」O(n) 解。冷冻期 / 手续费 / 限 k 次都是在这套「持股-不持股」状态机上加状态、改转移。

简化版

详细版