题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:

输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路

和买卖股票的最佳时机 II很相似，区别在于，买入股票时应该根据2天前没股票的状态考虑，即转移方程变为： $$\begin{array}{rl}dp[i][0]& =max(dp[i-1][0],dp[i-1][1]+prices[i])\\ dp[i][1]& =max(dp[i-1][1],dp[i-2][0]-prices[i])\end{array}$$

dp_1实际上仍然能用一个变量来表示，dp_0需要用2个变量，这里嫌麻烦直接用list了

代码

class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices or len(prices) < 2: return 0 dp_0 = [0, max(0, -prices[0] + prices[1])] dp_1 = [-prices[0], max(-prices[0], -prices[1])] for each_price in prices[2:]: new_dp_0 = max(dp_0[-1], dp_1[-1] + each_price) new_dp_1 = max(dp_1[-1], dp_0[-2] - each_price) dp_0.append(new_dp_0) dp_1.append(new_dp_1) return dp_0[-1]