leetcode 188 股票买卖

股票系列问题这样两种方法求解。
采用和股票问题3一样的方法，假设股票一天可以多次买卖，因为多次买卖利润为0,所以不会影响结果。
注意所有的题都是 买和卖其中选择一个算一次操作就可以。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices)==0:
            return 0
        buy=[-prices[0] for _ in range(k+1)]
        sell=[0 for _ in range(k+1)]
        for i in range(len(prices)):
            for j in range(1,k+1):
                buy[j]=max(buy[j],sell[j-1]-prices[i])#这里把卖出看作一次操作
                sell[j]=max(sell[j],buy[j]+prices[i])#买不算一次操作

        return sell[k]

使用动态规划方法。
状态为三种，一种指天数，一种指现在手里是否持股，一种是已经进行几次操作了(买或卖计算一次)
设置数组dp[i][2][k]
然后根据遍历 i 和 k 来转移状态。
dp[i][1][k]=max(dp[i-1][1][k],dp[i-1][0][k-1]-prices[i])#买看作计算操作
dp[i][0][k]=max(dp[i-1][0][k],dp[i-1][1][k]+prices[i])#这里不是dp[i-1][1][k-1]+prices[i] 因为卖不算一次操作。当然也可以把卖看作操作，然后买不算。

这里需要注意时间的问题，因为k会很大，又因为操作是一天一次那么买和卖隔了一天，所以看下len(prices)/2(最大的k交易次数) 和k 哪个比较小。

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

        if len(prices)<=1:
            return 0
        if k==0:
            return 0

        k=min(k,len(prices)//2)
        dp=[[[0 for _ in range(k+1)] for _ in range(2)]for _ in range(len(prices))]


        for i in range(k+1):
            dp[0][0][i]=0
            dp[0][1][i]=-prices[0]

        for  i in range(1,len(prices)):

                for t in range(1,k+1):

                    dp[i][0][t]=max(dp[i-1][0][t],dp[i-1][1][t-1]+prices[i])
                    dp[i][1][t]=max(dp[i-1][1][t],dp[i-1][0][t]-prices[i])

        return dp[len(prices)-1][0][k]

以卖为一次操作。

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

        if len(prices)<=1:
            return 0
        if k==0:
            return 0

        k=min(k,len(prices)//2)
        dp=[[[0 for _ in range(k+1)] for _ in range(2)]for _ in range(len(prices))]


        for i in range(k+1):
            dp[0][0][i]=0
            dp[0][1][i]=-prices[0]
        #for t in range(1,k+1):
        for  i in range(1,len(prices)):
                dp[i][1][0]=max(dp[i-1][1][0],-prices[i])
                #for  i in range(1,len(prices)):
                for t in range(1,k+1):
                    dp[i][1][t]=max(dp[i-1][1][t],dp[i-1][0][t]-prices[i])
                    dp[i][0][t]=max(dp[i-1][0][t],dp[i-1][1][t-1]+prices[i])
                    #dp[i][1][t]=max(dp[i-1][1][t],dp[i-1][0][t]-prices[i])

        return dp[len(prices)-1][0][k]