股票交易系列：多狀態 DP 的典範#

股票買賣問題是 LeetCode 上的經典系列（121, 122, 123, 188, 309, 714），也是面試高頻題。這類問題的核心在於構建一個通用的動態規劃框架，能夠處理各種交易限制。

問題變體總覽#

題號題目交易次數特殊限制
121買賣股票的最佳時機最多 1 次無
122買賣股票的最佳時機 II無限次無
123買賣股票的最佳時機 III最多 2 次無
188買賣股票的最佳時機 IV最多 k 次無
309最佳買賣股票時機含冷凍期無限次賣出後隔一天才能買
714買賣股票的最佳時機含手續費無限次每次交易扣手續費

基礎題目的直觀解法#

LeetCode 121：只能買賣一次#

核心思路：在歷史最低點買入，之後的最高點賣出。

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }

    return maxProfit;
}

LeetCode 122：可以無限次交易#

核心思路：只要明天比今天貴，今天就買、明天就賣。

int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

雖然 121 和 122 可以用貪心或單次走訪解決，但面對複雜限制（k 次交易、冷凍期、手續費），我們需要構建通用的 DP 框架。

通用動態規劃框架#

為什麼需要升維？#

如果只用一維陣列 dp[i]（第 i 天的最大利潤），會丟失關鍵資訊：

  • 持有狀態：手中有沒有股票？
  • 交易次數：已經交易了幾次？

核心洞察

  • 買入前提：手中沒有股票
  • 賣出前提：手中持有股票
  • 次數限制：買入時需檢查剩餘交易額度

三維狀態定義#

dp[i][k][j] 表示：

  • i：第 i 天（0 到 n-1）
  • k：已進行的交易次數（0 到 K）
  • j：持有狀態（0 = 不持有，1 = 持有）

狀態轉移方程#

當天結束時「不持有」股票：dp[i][k][0]

$$ dp[i][k][0] = \max \begin{cases} dp[i-1][k][0] & \text{（休息：昨天就沒有）} \ dp[i-1][k][1] + prices[i] & \text{（賣出：昨天有，今天賣）} \end{cases} $$

當天結束時「持有」股票：dp[i][k][1]

$$ dp[i][k][1] = \max \begin{cases} dp[i-1][k][1] & \text{（休息：昨天就持有）} \ dp[i-1][k-1][0] - prices[i] & \text{（買入：消耗一次交易額度）} \end{cases} $$

關鍵細節 買入操作會消耗一次交易額度，因此狀態從 k-1 轉移而來。 這是連接不同交易次數階層的關鍵橋樑。

最終結果#

最後一天且不持有股票的所有可能交易次數中的最大值：

$$Result = \max_{k=0}^{K} (dp[n-1][k][0])$$

通用程式碼框架#

至多 K 次交易的通用解法
int maxProfit(int K, int[] prices) {
    int n = prices.length;
    if (n == 0) return 0;

    // dp[i][k][j]: 第 i 天，已交易 k 次，持有狀態 j
    int[][][] dp = new int[n][K + 1][2];

    // 初始化
    for (int k = 0; k <= K; k++) {
        dp[0][k][0] = 0;
        dp[0][k][1] = -prices[0];  // 第一天買入
    }

    for (int i = 1; i < n; i++) {
        for (int k = 1; k <= K; k++) {
            // 不持有：休息 or 賣出
            dp[i][k][0] = Math.max(
                dp[i - 1][k][0],
                dp[i - 1][k][1] + prices[i]
            );

            // 持有：休息 or 買入（消耗一次交易額度）
            dp[i][k][1] = Math.max(
                dp[i - 1][k][1],
                dp[i - 1][k - 1][0] - prices[i]
            );
        }
    }

    // 找最大值
    int maxProfit = 0;
    for (int k = 0; k <= K; k++) {
        maxProfit = Math.max(maxProfit, dp[n - 1][k][0]);
    }
    return maxProfit;
}

特定 K 值的優化#

K = 2 的變數優化法#

當 K = 2 時，可以將狀態展開為四個變數：

int maxProfit(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;

    for (int price : prices) {
        buy1 = Math.max(buy1, -price);            // 第一次買入
        sell1 = Math.max(sell1, buy1 + price);    // 第一次賣出
        buy2 = Math.max(buy2, sell1 - price);     // 第二次買入
        sell2 = Math.max(sell2, buy2 + price);    // 第二次賣出
    }

    return sell2;
}

變數含義

  • buy1：第一次買入後的餘額（負值）
  • sell1：第一次賣出後的利潤
  • buy2：在第一次獲利基礎上，第二次買入後的餘額
  • sell2：第二次賣出後的總利潤

特殊限制的處理#

含冷凍期 (Cooldown)#

賣出後，第二天無法買入，必須隔一天。

修改方案：買入時的狀態轉移改為依賴前天

$$dp[i][1] = \max(dp[i-1][1], dp[i-2][0] - prices[i])$$

含冷凍期 Java 實現
int maxProfit(int[] prices) {
    int n = prices.length;
    if (n <= 1) return 0;

    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (int i = 1; i < n; i++) {
        // 不持有：休息 or 賣出
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

        // 持有：休息 or 買入（需要看前天的狀態）
        if (i >= 2) {
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        } else {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
    }

    return dp[n - 1][0];
}

含手續費 (Transaction Fee)#

每次交易需要扣除手續費。

修改方案：在賣出時扣除手續費

$$dp[i][0] = \max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)$$

含手續費 Java 實現
int maxProfit(int[] prices, int fee) {
    int n = prices.length;
    int[][] dp = new int[n][2];

    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (int i = 1; i < n; i++) {
        // 不持有：休息 or 賣出（扣手續費）
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);

        // 持有：休息 or 買入
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

    return dp[n - 1][0];
}

狀態機視角#

股票交易問題可以用狀態機來理解：

                ┌──────────┐
          Buy   │          │  Rest
    ┌──────────►│  持有    │◄──────┐
    │           │          │       │
    │           └────┬─────┘       │
    │                │             │
    │           Sell │             │
    │                ▼             │
┌───┴────┐     ┌──────────┐       │
│        │Rest │          │  Rest │
│ 不持有 │◄────│  冷凍期  │       │
│        │     │ (可選)   │       │
└────────┘     └──────────┘       │
    │                              │
    └──────────────────────────────┘

解題策略總結#

情況K 值策略
只能交易 1 次K=1記錄歷史最低價
可以無限交易K=∞累加所有正收益
至多交易 2 次K=2變數優化法 or 通用 DP
至多交易 k 次K=k三維 DP
含冷凍期K=∞買入依賴前天狀態
含手續費K=∞賣出時扣除手續費

學習建議

  1. 從 K=1 開始，理解基本轉移邏輯
  2. 嘗試 K=2，比較變數法與標準 DP 法
  3. 挑戰 K=任意值，掌握通用解法
  4. 用通用解法回頭解決 K=2，體驗通解的威力
Backward 經典DP問題 DP實戰指南 Forward