public int maxProfit(int[] prices) {
/*
重点在于表述状态转移方程，也就是从递归的角度描述，然后反向执行
首先股票包含的状态为sell buy cool
从递归的角度来看：
股票在第i天能够执行的操作有 buy sell ,并且在卖和买之间有一天的cool,但是在买和卖之间同样存在隐藏的cool_hidden;
判断第i天四种操作获取的最大利润
buy[i]:cool[i-1]-price[i];
cool_hidden[i]:cool_hidden[i-1];buy[i-1];
sell[i]:cool_hidden[i-1]+price[i];buy[i-1]+price[i];
cool[i]:sell[i-1];cool[i-1];
这个状态太长，开始降维合并：
首先，cool_hidden 可以合并到buy:hold操作就包含了buy和cool_hidden;
cool也可以列合并到sell：unhold操作包含sell和cool
hold[i]=max(hold[i-1],unhold[i-2]-price[i]);
unhold[i]=max(unhold[i-1],hold[i-1]+price[i]);
*/
int n = prices.length;
if(n<2)
return 0;
int[] hold=new int[n];
int[] unhold=new int[n];
hold[0]=-prices[0];
unhold[0]=0;
hold[1]=Math.max(hold[0],unhold[0]-prices[1]);
unhold[1]=Math.max(unhold[0],hold[0]+prices[1]);
for(int i=2;i<n;i++){
hold[i]=Math.max(hold[i-1],unhold[i-2]-prices[i]);
unhold[i]=Math.max(unhold[i-1],hold[i-1]+prices[i]);
}
return Math.max(hold[n-1],unhold[n-1]);
}
}[leetcode309] Best Time to Buy and Sell Stock with Cooldown
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Description Say you have an array for which the ith eleme...
- Description Your are given an array of integers prices, f...
- 感觉不像股票系列，倒是很像house rubery那个题。dp function的含义是"sold[i]:第i天卖...
- 原题地址 https://leetcode.com/problems/best-time-to-buy-and-s...
