Best Time to Buy and Sell Stock IV

Solution

定义

• $dfs(i, j, 0)$：表示第 $i$ 天结束时，手里没有股票，已经完成了 $j$ 笔交易时的最大收益。
• $dfs(i, j, 1)$：表示第 $i$ 天结束时，手里持有股票，已经完成了 $j$ 笔交易时的最大收益。

状态转移方程

$\begin{aligned} dfs(i, j, 0) &= \max\Bigl(dfs(i - 1,\, j,\, 0),\;\; dfs(i - 1,\, j,\, 1) \;+\; prices[i]\Bigr) \\ dfs(i, j, 1) &= \max\Bigl(dfs(i - 1,\, j,\, 1),\;\; dfs(i - 1,\, j - 1,\, 0) \;-\; prices[i]\Bigr) \end{aligned}$

边界条件

• $dfs(-1, j) = -\infty$ —— 任何情况下，$j$ 都不可能为负
• $dfs(-1, j, 0) = 0$ —— 第 0 天结束时未持有股票，利润为 0
• $dfs(-1, j, 1) = -\infty$ —— 第 0 天结束时不可能持有股票

递归入口

$\max\bigl(dfs(n - 1,\, k,\, 0),\; dfs(n - 1,\, k,\, 1)\bigr) \;=\; dfs(n - 1,\, k,\, 0)$

DP Recursion

def maxProfit(self, k: int, prices: List[int]) -> int:
    n = len(prices)
    
    @cache
    def dfs(i, j, hold):
        if j < 0:
            return -inf
        if i < 0:
            return -inf if hold else 0

        if hold:
            return max(dfs(i-1, j, True), dfs(i-1, j-1, False) - prices[i])
        else:
            return max(dfs(i-1, j, False), dfs(i-1, j, True) + prices[i])
    
    return dfs(n-1, k, False)

DP Iteration

j 的范围是 [-1,k]，这一共有 k+2 个数。1:1 翻译成递推就需要 k+2 的数组大小。dp 数组中 j=0 对应着记忆化搜索中的 j=-1 的状态，也就是交易 -1 次的状态。注意这是不合法的，所以初始值一定是 $-\infty$。

def maxProfit(self, k: int, prices: List[int]) -> int:
    n = len(prices)

    dp = [[[-inf for _ in range(2)] for _ in range(k+2)] for _ in range(n+1)]
    for j in range(1, k+2):
        dp[0][j][0] = 0 # i < 0, not hold
    for i in range(1, n+1):
        for j in range(1, k+2):
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1])
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1])
    return dp[n][k+1][0]