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

给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入prices [3,3,5,0,0,3,1,4]输出6解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。示例 2输入prices [1,2,3,4,5]输出4解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。示例 3输入prices [7,6,4,3,1]输出0解释在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4输入prices [1]输出0提示1 prices.length 1050 prices[i] 105classSolution:defmaxProfit(self,prices:List[int])-int:max_k2nlen(prices)dp[[[0for_inrange(2)]for_inrange(max_k1)]for_inrange(n)]foriinrange(n):forkinrange(max_k,0,-1):ifi-1-1:# 处理 base casedp[i][k][0]0dp[i][k][1]-prices[i]continuedp[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])# 穷举了 n × max_k × 2 个状态正确。returndp[n-1][max_k][0]