LeetCode 714. 买卖股票的最佳时机含手续费

题目描述

给定一个整数数组prices，其中第i个元素代表了第i天的股票价格 ；非负整数fee代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释:

能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意

• 0<prices.length<=500000 < prices.length <= 50000
• 0<prices[i]<500000 < prices[i] < 50000
• 0<=fee<500000 <= fee < 50000

题解

按道理来说，这道题应该不难，但是想复杂了反而变得很麻烦。

对于 dp[i][j]dp[i][j]，定义为“第 ii 天结束时，持有股票(j=1j=1)或不持有股票(j=0j=0)的最大收益”
根据这一点，很容易得到下面的转移方程：
{dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i]−fee)dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i])\begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee) \\ dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) \end{cases}
解释为：如果今天不持有股票，可能是前一天也没持有，也可能是今天卖了；如果今天持有股票，有可能是前一天已持有，也可能是今天刚买的。
这样，只需要维护每天的收益值即可。原理上来说，能卖掉肯定比持有收益更大，最终结果应该是 dp[n−1][0]dp[n-1][0]。为了避免各种可能引入的问题，这里还是比较了下数值。

以下是开始时的错误思路

在最初想的时候，考虑到对于 [3,1,2,3,4,5,4][3,1,2,3,4,5,4] 的情况，根据贪心可以只考虑 [3,1,5,4][3,1,5,4] 这些极值点。获取极值点后可以得到差分数组 [−2,4,−1][-2,4,-1]。这样，动态规划的结果应该是类似这样的方程:
dp[i]=dp[i−2]+max(prices[i]+prices[i−1],prices[i]−fee)dp[i] = dp[i-2] + max(prices[i] + prices[i-1], prices[i] - fee)
也即，当前的“上升期”是和上一个“上升期”连起来，还是单独作为一个“上升期”（作为单独的一次交易）。但是这需要考虑很多额外的边界情况，而且需要更大的内存占用。

尽管最初读题的时候，有考虑到上面的根据是否持有股票来进行动态规划，但是由于陷入了“上升期”的考虑，认为可能需要考虑之前所有的“上升期”，从而导致时间复杂度变为 O(n2)O(n^2)。从思路上来说，被自己设计的“上升期”的优化给限制了。
也即，没有确定转移方程是否仅有 dp[i−1]dp[i-1] 转移而来。

避免该问题的结论是：不应该在状态不好的时候刷题，不然就算等状态好了，思路还是会被带偏。

代码

int maxProfit(int* prices, int pricesSize, int fee){
    int dp[2][2]; dp[0][0]=0; dp[0][1] = -prices[0];
    for (int i=1; i<pricesSize; ++i) {
        int t=i&1,p=!t;
        dp[t][0] = fmax(dp[p][0], dp[p][1]+prices[i]-fee);
        dp[t][1] = fmax(dp[p][1], dp[p][0]-prices[i]);
    }
    int lst = (pricesSize-1)&1;
    return fmax(0, fmax(dp[lst][0], dp[lst][1]));
}