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 <= 50000$
• $0 < prices[i] < 50000$
• $0 <= fee < 50000$

题解

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

对于 $dp[i][j]$，定义为“第 $i$ 天结束时，持有股票($j=1$)或不持有股票($j=0$)的最大收益”
根据这一点，很容易得到下面的转移方程：
$\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]$。为了避免各种可能引入的问题，这里还是比较了下数值。

以下是开始时的错误思路

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

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