leetcode 123 股票利润3

动态规划，分析会产生几种状态。
哪天的股票，当天是否持有，当天已经买卖过几次,是否持有股票分两种情况，持有还是不持有；已经买卖过几次，分三种，因为题目要求至多2次买卖，分别是0次，1次，2次。
也就是组合出来每天有6种情况。
然后分别分析这六种情况的状态转移。
dp[i][0][0]=dp[i-1][0][0]# 没持有，也没卖
dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][0]+prices[i])#当前没有持有，但是已经买卖过一次，那就有可能是今天卖的第一次，要么是已经就已经卖过第一次了
dp[i][0][2]=max(dp[i-1][0][2],dp[i-1][1][1]+prices[i])#当前没持有，但是买卖过两次，要么是之前就买卖过两次，要么是之前持有且买卖过一次
dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][0]-prices[i])#当前持有，没有买卖过，要么之前就持有，要么之前没持有才买入
dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][1]-prices[i])#当前持有，同时买卖过一次，要么之前也是这个状态，要么是刚刚买入
dp[i][1][2]=float('-inf')不存在值

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[[0,0,0],[0,0,0]] for _ in range(len(prices))]
        dp[0][0][0]=0
        dp[0][1][0]=-prices[0]
        dp[0][0][1]=float('-inf')
        dp[0][0][2]=float('-inf')
        dp[0][1][1]=float('-inf')
        dp[0][1][2]=float('-inf')


        for i in range(1,len(prices)):
            dp[i][0][0]=0
            dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])
            dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])
            dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])
            dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])
            dp[i][1][2]=float('-inf')
        #
        return max(dp[len(prices)-1][0][2],dp[len(prices)-1][0][1],0)

把它看作四个状态，buy1,buy2,sell1,sell2，将这四种状态进行转移。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:      

        buy1,buy2,sell1,sell2=-prices[0],-prices[0],0,0
        for i in range(1,len(prices)):

            buy1=max(-prices[i],buy1)
            sell1=max(buy1+prices[i],sell1)
            buy2=max(sell1-prices[i],buy2)
            sell2=max(buy2+prices[i],sell2)

        return max(sell1,sell2)