题目

题解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        # 状态定义 dp[i][j][k]代表在第i天，被允许完成j次交易时，持有或者不持有的最大利润。k=0代表不持有，k=1代表持有
        dp = [[[0 for k in range(2)] for j in range(3)] for i in range(N)]

        for i in range(N):
        	# 注意遍历范围 
            for j in range(1, 3):
                # badcase
                if i - 1 == -1:
                    dp[i][j][0] = 0
                    dp[i][j][1] = -prices[i]
                else:
                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

        return dp[N-1][2][0]