sell[i]
表示第i天未持股时,获得的最大利润,buy[i]
表示第i天持有股票时,获得的最大利润。sell[i]
,最大利润有两种可能,一是今天没动作跟昨天未持股状态一样,二是今天卖了股票,所以状态转移方程如下:sell[i] = max{sell[i - 1], buy[i-1] + prices[i]}
buy[i]
,最大利润有两种可能,一是今天没动作跟昨天持股状态一样,二是前天卖了股票,今天买了股票,因为 cooldown 只能隔天交易,所以今天买股票要追溯到前天的状态。状态转移方程如下:buy[i] = max{buy[i-1], sell[i-2] - prices[i]}
sell[n - 1]
,表示最后一天结束时,手里没有股票时的最大利润。O(n)
,不过由于sell[i]
仅仅依赖前一项,buy[i]
仅仅依赖前两项,所以可以优化到O(1)
,具体见第二种代码实现。