Description
給定股票每天的價格陣列，可以多次買賣但賣出後隔天為冷卻期（不能買入）。求最大利潤。
Example:
Input: prices = [1,2,3,0,2] Output: 3 (買 1 賣 3，冷卻，買 0 賣 2)
Intuition#
用狀態機思維：每天有「持有股票」、「不持有且在冷卻」、「不持有且非冷卻」三種狀態。
- 定義三種狀態：
hold：持有股票的最大利潤sold：今天剛賣出（明天進入冷卻）rest：不持有且非冷卻（可以買入）
- 狀態轉移：
hold = max(hold, rest - price)（繼續持有 或 今天買入）sold = hold + price（今天賣出）rest = max(rest, sold)（繼續休息 或 冷卻結束）
Approaches#
1: 2D DP Table#
- 概念: 用
dp[i][state]記錄第 i 天各狀態的最大利潤，state 為 0（rest）、1（hold）、2（sold）。 - 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun maxProfit(prices: IntArray): Int {
val n = prices.size
if (n <= 1) return 0
// dp[i][0] = rest, dp[i][1] = hold, dp[i][2] = sold
val dp = Array(n) { IntArray(3) }
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
for (i in 1 until n) {
dp[i][0] = maxOf(dp[i - 1][0], dp[i - 1][2])
dp[i][1] = maxOf(dp[i - 1][1], dp[i - 1][0] - prices[i])
dp[i][2] = dp[i - 1][1] + prices[i]
}
return maxOf(dp[n - 1][0], dp[n - 1][2])
}
}⭐2: 狀態機（空間優化）#
- 概念: 三個狀態只依賴前一天的值，用三個變數即可。
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun maxProfit(prices: IntArray): Int {
if (prices.size <= 1) return 0
var rest = 0
var hold = -prices[0]
var sold = 0
for (i in 1 until prices.size) {
val prevRest = rest
val prevHold = hold
val prevSold = sold
rest = maxOf(prevRest, prevSold)
hold = maxOf(prevHold, prevRest - prices[i])
sold = prevHold + prices[i]
}
return maxOf(rest, sold)
}
}🔑 Takeaways#
- Pattern: 狀態機 DP — 定義多個狀態並描述轉移關係
- 關鍵技巧: 股票問題系列都可以用狀態機建模（持有/未持有/冷卻）；注意更新順序，需要用前一天的值