LeetCode-188-买卖股票的最佳时机 IV

解题思路

1. 第一次买入： 从初始状态转换而来，或者第一次买入后保持不动
   dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][0]-prices[i])

2. 第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
   dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][1]+prices[i])

3. 第二次买入： 从第一次卖出转换而来，或者第二次买入后保持不动
   dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][1][0]-prices[i])

4. 第二次卖出： 从第二次买入转换而来，或者第二次卖出后保持不动
   dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][1][1]+prices[i])

5. 第三次买入：
   dp[i][2][1] = max(dp[i-1][2][1],dp[i-1][2][0]-prices[i])

6. 第三次卖出：
   dp[i][3][0] = max(dp[i-1][3][0],dp[i-1][2][1]+prices[i])

...

7. 第k次买入
   dp[i][j-1][1] = max(dp[i-1][j-1][1], dp[i-1][j-1][0]-prices[i])

8. 第k次卖出
   dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])

9. 第k+1次买入
   dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]-prices[i])

Python3代码

  class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0
        n = len(prices)

        if k > n//2:
            dp0, dp1 = 0, -prices[0]
            for i in range(1,n):
                tmp = dp0
                dp0 = max(dp0,dp1+prices[i])
                dp1 = max(dp1,tmp-prices[i])
            return max(dp0,dp1)

        dp = [[[0, 0] for _ in range(k+1)] for _ in range(n)]
        for i in range(k+1):
            dp[0][i][0] = 0 
            dp[0][i][1] = -prices[0]
        for i in range(1, n):
            for j in range(1, k+1):
                # 处理第k次买入
                dp[i][j-1][1] = max(dp[i-1][j-1][1], dp[i-1][j-1][0]-prices[i])
                # 处理第k次卖出
                dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])
        return dp[-1][k][0]