[LeetCode]Best Time to Buy and Sell Stock with Cooldown

这道题和Best Time to Buy and Sell Stock II是类似的。唯一的区别就是卖了之后再买需要cool down，之前我们是用Greedy的做法，但是如果我们用dp[i]来表示前i + 1天能够获得的最大利润(不限交易次数)，对于没有冷却期的情况:

• dp[i] = max(dp[j] + prices[i] - prices[j]), where j <= i

加上冷却期之后，就会变成:

• dp[i] = max(max(dp[j - 2] + prices[i] - prices[j]), prices[i] - prices[0], prices[i] - prices[1]), where 2<=j <= i

时间复杂度O(n)，我们可以开一个dp array这样需要O(n)的空间，代码如下：



也可以用滚动数组优化成常数空间，代码如下：