309. Best Time to Buy and Sell Stock with Cooldown
可以画出一个状态机:(无,rest)代表刚卖完股票,不能操作
例如对于有股票状态来说:
(有股票):1.卖掉 -> (无股票,rest); 2.rest -> (有股票)
所以可以写出dp方程式:
这里无股票用s0表示,有股票用s1表示,刚卖完股票用s2表示
s0[i] = max(s0[i - 1], s2[i - 1])
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i])
s2[i] = s1[i - 1] + prices[i]
const maxProfit = function (prices) {
if (prices.length <= 1) {
return 0;
}
let s0 = [0], s1 = [-prices[0]], s2 = [Number.MIN_SAFE_INTEGER];
// 这里无股票用s0表示,有股票用s1表示,刚卖完股票用s2表示
for (let i = 1; i < prices.length; i++) {
s0[i] = Math.max(s0[i - 1], s2[i - 1]);
s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
s2[i] = s1[i - 1] + prices[i];
}
return Math.max(s0[prices.length - 1], s1[prices.length - 1], s2[prices.length - 1]);
};
这种是比较好理解的方法
理解题意之后其实可以直接写出dp方程式:
对于每一天,有三种动作,buy, sell, cooldown, sell 和 cooldown 可以合并成一种状态,因为手里最终没有股票。最终需要的结果是 sell,即手里股票卖了获得最大利润。我们可以用两个数组来记录当前持股和未持股的状态,令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]}
然后巧妙地用几个变量来取代dp数组
const maxProfit = function (prices) {
let sell = 0, prev_sell = 0, buy = Number.MIN_SAFE_INTEGER, prev_buy;
// 这里无股票用s0表示,有股票用s1表示,刚卖完股票用s2表示
for (let i = 0; i < prices.length; i++) {
// buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i])
// sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i])
// 此时,prev_buy等于上上个循环中的prev_buy,prev_sell同理
// buy和sell就是上个循环中的buy和sell
prev_buy = buy;
buy = Math.max(prev_buy, prev_sell - prices[i])
prev_sell = sell;
sell = Math.max(prev_sell, prev_buy + prices[i])
}
return sell;
};
const maxProfit = function (prices) {
let sell = 0, prev_sell = 0, buy = Number.MIN_SAFE_INTEGER, prev_buy;
for (let i = 0; i < prices.length; i++) {
prev_buy = buy;
buy = prev_buy > prev_sell - prices[i] ? prev_buy : prev_sell - prices[i];
prev_sell = sell;
sell = prev_sell > prev_buy + prices[i] ? prev_sell : prev_buy + prices[i];
}
return sell;
};