代码随想录day50|123. 买卖股票的最佳时机 III188. 买卖股票的最佳时机 IV

123. 买卖股票的最佳时机 III

class Solution:def maxProfit(self, prices: List[int]) -> int:dp=[[0]*5 for _ in range(len(prices))]dp[0][0]=0dp[0][1]=-prices[0]dp[0][2]=0dp[0][3]=-prices[0]dp[0][4]=0for i in range(1,len(prices)):dp[i][0] = dp[i-1][0]dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])return dp[len(prices)-1][4]

188. 买卖股票的最佳时机 IV

class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:dp = [[0]* (2*k+1) for _ in range(len(prices))]dp[0][0] = 0j=1while j < 2*k: dp[0][j] = -prices[0]j+=2for i in range(1,len(prices)):j=0while j < 2*k-1:dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i])dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])j+=2return dp[len(prices)-1][2*k]