题解 | #买卖股票的最好时机(四)#

买卖股票的最好时机(四)，动态规划，时间O(kn)，空间O(k)

买需在卖后，卖需在买后，股票的持有和卖出状态不能统一成一个状态，需要分别表示两个状态。同样的，第j次交易需要在第j-1次交易完成（买入卖出）之后，不能统一成一个操作，需要分别表示每一次操作的两个状态，那么k次交易就有2k个状态。从子问题规模为1开始，逐步增加规模，最后到原问题规模，此时第k次不持有状态即为解。根据子问题更新状态时，只与前一个子问题的状态有关，所以不需要单独表示每个子问题的2k个状态。

class Solution:
    def maxProfit(self , prices: List[int], k: int) -> int:
        dp = [[0]*2 for _ in range(k)]        # 每天都有2*k种状态，为第j次持有或者不持有状态
        for i in range(k):
            dp[i][1] = -prices[0]             # 初始化第j次持有的最大收益    
        for i in range(1, len(prices)):
            for j in range(k):                
                if j == 0:                    # 第一次持有状态，延续之前状态或者忽视之前状态重新买入
                    dp[j][1] = max(dp[j][1], 0-prices[i])
                else:
                    # 第j>0次持有状态，延续之前状态或者在第j-1次卖出（不持有）状态下买入
                    dp[j][1] = max(dp[j][1], dp[j-1][0]-prices[i]) 
                # 第j次卖出后的不持有状态，延续之前状态或者在第j次持有状态下卖出
                dp[j][0] = max(dp[j][0], dp[j][1]+prices[i])      
        return dp[k-1][0]