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

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

問題變體總覽#

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

基礎題目的直觀解法#

只能買賣一次（最多 1 次）#

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

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var maxProfit = 0

    for (price in prices) {
        minPrice = minOf(minPrice, price)               // 先更新最低價
        maxProfit = maxOf(maxProfit, price - minPrice)  // minPrice ≤ price，不會溢位
    }

    return maxProfit
}

可以無限次交易#

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

fun maxProfit(prices: IntArray): Int {
    var profit = 0
    for (i in 1 until prices.size) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1]
        }
    }
    return profit
}

雖然買賣股票的最佳時機 ↗和買賣股票的最佳時機 II ↗可以用貪心或單次走訪解決，但面對複雜限制（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 次交易的通用解法
fun maxProfit(K: Int, prices: IntArray): Int {
    val n = prices.size
    if (n == 0) return 0

    // dp[i][k][j]: 第 i 天，已交易 k 次，持有狀態 j
    val dp = Array(n) { Array(K + 1) { IntArray(2) } }

    // 初始化：第一天
    for (k in 0..K) {
        dp[0][k][0] = 0
        dp[0][k][1] = -prices[0]  // 第一天買入
    }

    for (i in 1 until n) {
        for (k in 1..K) {
            // 不持有：休息 or 賣出
            dp[i][k][0] = maxOf(
                dp[i - 1][k][0],
                dp[i - 1][k][1] + prices[i],
            )

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

    // 找最大值
    var maxProfit = 0
    for (k in 0..K) {
        maxProfit = maxOf(maxProfit, dp[n - 1][k][0])
    }
    return maxProfit
}

特定 K 值的最佳化#

K = 2 的變數最佳化法#

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

fun maxProfit(prices: IntArray): Int {
    var buy1 = Int.MIN_VALUE   // 每輪都會先被更新，不會參與加法而溢位
    var sell1 = 0
    var buy2 = Int.MIN_VALUE
    var sell2 = 0

    for (price in prices) {
        buy1 = maxOf(buy1, -price)          // 第一次買入
        sell1 = maxOf(sell1, buy1 + price)  // 第一次賣出
        buy2 = maxOf(buy2, sell1 - price)   // 第二次買入
        sell2 = maxOf(sell2, buy2 + price)  // 第二次賣出
    }

    return sell2
}

變數含義

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

特殊限制的處理#

含冷凍期 (Cooldown)#

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

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

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

含冷凍期
fun maxProfit(prices: IntArray): Int {
    val n = prices.size
    if (n <= 1) return 0

    val dp = Array(n) { IntArray(2) }
    dp[0][0] = 0
    dp[0][1] = -prices[0]

    for (i in 1 until n) {
        // 不持有：休息 or 賣出
        dp[i][0] = maxOf(dp[i - 1][0], dp[i - 1][1] + prices[i])

        // 持有：休息 or 買入（需要看前天的狀態）
        dp[i][1] = if (i >= 2) {
            maxOf(dp[i - 1][1], dp[i - 2][0] - prices[i])
        } else {
            maxOf(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)$$

含手續費
fun maxProfit(prices: IntArray, fee: Int): Int {
    val n = prices.size
    val dp = Array(n) { IntArray(2) }

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

    for (i in 1 until n) {
        // 不持有：休息 or 賣出（扣手續費）
        dp[i][0] = maxOf(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)

        // 持有：休息 or 買入
        dp[i][1] = maxOf(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