又是一道找到了状态转移方程, 就可以迎刃而解的问题
但是状态转移方程不好找啊
分析题目:
每一天的四种状态: 买进, 卖出, 冷冻期, 什么都不做
每天的状态排列遵循: 买... 卖冷... 买... 卖冷... 其中... 代表什么都不做的日子, 可能有多个
因为有的日子什么都不做, 没办法指明某一天到底进行了哪种操作, 所以将状态定为 "这一天及之前进行的最后操作"
第 i 天及以前, 进行的最后操作为买进, 所获得的最大收益: sell[i]
类似地定义 buy[i] ,cool[i]
状态转移方程:
- sell[i]=buy[i-1]+price[i]
- buy[i]=max(cool[i-1]-prices[i],buy[i])
- cool[i]=max(sell[i-1],cool[i-1])
代码:
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- int len = prices.size();
- if (len == 0)return 0;
- vector<int> sell(len), buy(len), cool(len);
- sell[0] = 0;
- buy[0] = -1*prices[0];
- cool[0] = 0;
- for (int i = 1;i < len;i++) {
- sell[i] = buy[i - 1] + prices[i];
- buy[i] = max(cool[i - 1] - prices[i], buy[i - 1]);
- cool[i] = max(sell[i - 1], cool[i - 1]);
- }
- int ans = max(sell[len-1], buy[len-1]);
- ans=max(ans,cool[len - 1]);
- return ans;
- }
- };
来源: http://www.bubuko.com/infodetail-3100056.html