[LeetCode]Best Time to Buy and Sell Stock with Transaction Fee

用DP[i]表示前i + 1天的最大利润，我们有递推公式：

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

递推公式取dp[j - 1] + prices[i] - prices[j] - fee或者dp[j] + prices[i] - prices[j] - fee都是可以的，不会影响最终的结果。时间复杂度O(n)，空间复杂度O(n):

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

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

我们可以优化到常数空间，代码如下：

	class Solution {
	public:
	int maxProfit(vector<int>& prices, int fee) {
	int len = prices.size();
	if(len < 2)return 0;
	//dp[i] represents maxProfit in first i + 1 days, so we have
	//localMax = max(max(dp[j - 1] + prices[i] - prices[j] - fee), prices[i] - prices[0] - fee), where 1 <= j < i
	//dp[i] = max(dp[i - 1], localMax)
	int maxDiff = - prices[1], globalMax = max(0, prices[1] - prices[0] - fee);
	for(int i = 2; i < len; ++i)
	{
	int localMax = max(maxDiff + prices[i] - fee, prices[i] - prices[0] - fee);
	int currMax = max(globalMax, localMax);
	maxDiff = max(maxDiff, globalMax - prices[i]);
	globalMax = currMax;
	}
	return globalMax;
	}
	};

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