leetcode 309 Best Time to Buy and Sell Stock with Cooldown 详细解答
解法1
参照leetcode 122, 解法几乎一样
但这里需要三个数组，
sell: 每次卖出股票后自身的收益
buy: 每次买入股票后自身的收益
cooldown: 冷冻股票后自身的收益
根据题意很明显：cooldown[i] = sell[i-1]
因为题目说在卖出之后需要一个冷冻期
sell[i] = max( sell[i-1], buy[i-1] + prices[i] )
buy[i] = max( buy[i-1], cooldown[i-1] - prices[i] )
代码如下：
进阶2
一般动态规划所设的数组都可以用O(1)的方法替代。
但在这儿需要用到前一个状态。
所以代码如下：
这样时间复杂度还是O(N)，但空间复杂度是O(1)