[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)的空间，代码如下：

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	int len = prices.size();
	if(len < 2)return 0;
	//dp[i] represent maxProfit in first i + 1 days
	//localMax = max(max(dp[j - 2] + prices[i] - prices[j], where 2 <= j <= i), prices[i] - prices[0], prices[i] - prices[1])
	//we maintain the max value of dp[j - 2] - prices[j]
	//dp[i] = max(dp[i - 1], localMax);
	vector<int> dp(len, 0);
	dp[1] = max(prices[1] - prices[0], 0);
	int maxDiff = dp[0] - prices[2];
	for(int i = 2; i < len; ++i)
	{
	maxDiff = max(dp[i - 2] - prices[i], maxDiff);
	int localMax = max(maxDiff + prices[i], max(prices[i] - prices[0], prices[i] - prices[1]));
	dp[i] = max(dp[i - 1], localMax);
	}
	return dp[len - 1];
	}
	};

view raw Best Time to Buy and Sell Stock with Cooldown.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	int len = prices.size();
	if(len < 2)return 0;
	vector<int> dp(2, 0);
	dp[1] = max(0, prices[1] - prices[0]);
	int maxDiff = dp[0] - prices[2], e = 0;
	for(int i = 2; i < len; ++i, e ^= 1)
	{
	maxDiff = max(maxDiff, dp[e] - prices[i]);
	int localMax = max(maxDiff + prices[i], max(prices[i] - prices[0], prices[i] - prices[1]));
	dp[e] = max(dp[e ^ 1], localMax);
	}
	return dp[e ^ 1];
	}
	};

view raw Best Time to Buy and Sell Stock with Cooldown.cpp hosted with ❤ by GitHub