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

class Solution:
    def maxProfit(self, k, price):
        if not prices:
            return 0
        n=len(prices)
        max_k=n//2
        if k >= max_k:#等同于k无穷大
            res=0
            for i in range(n-1):
                res+=max(0,price[i+1]-price[i])#多次买入卖出，叠加利润差即可
            return res
        else:
            max_k=k
        dp=[[0]*2 for _ in range(k+1)]
        for i in range(max_k+1):
            dp[0][i][1]=-prices[0]
        for i in range(1,n):
            for k in range(1,max_k+1)：
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
        return dp[n-1][max_k][0]