一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 238|回复: 0
收起左侧

[动态规划] Leetcode 309 Best Time to Buy and Sell Stock with Cooldown小白解法

[复制链接] |试试Instant~ |关注本帖
queenjuliana 发表于 2016-10-27 07:35:39 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一道DP题,看了很久lc的discuss最后画了个表格算是搞懂了,把过程在下面写一下,希望能帮助到和我一样转专业的小白朋友们,大牛们可以提提建议哈(* ̄▽ ̄*)


1.      状态

以下都表示现在(今天)的状态。

hold:持有股票(包括今天新买股票和继续持有昨天的股票)

sell 卖股票

rest 休息 (包括昨天卖了今天休息,和继续休息)

今天的利润为Sellrest中较大者。

另有prevHold, prevSell, prevRest表示昨天的状态。

2.      方程

price 表示今天的股票价格,买入时利润-price,卖出时利润+price

hold = Math.max (prevHold, prevRest - price); //我觉得用hold能更好表达这个状态,如果用buy,搞得好像可以连续buy,其实只是一直持有。

sell = prevHold + price;

rest = Math.max(prevRest, prevSell);

3.      初始值

prevHold = -price[0];

prevSell = 0;

prevRest = 0;

price[1]开始,循环条件 < price.length,返回sellrest中较大者

  
profit
  
  
hold
  
  
sell
  
  
rest
  
  
Price
  
  
0
  
  
-2
  
  
0
  
  
0
  
  
2
  
  
Max(4,0) = 3
  
  
Max(-2,0-5)=-2
  
  
-2 + 5 = 3
  
  
Max(0, 0) = 0
  
  
5
  
  
Max(-1,3) = 3
  
  
Max(-2, 0-1) = -1
  
  
-2+ 1 = -1
  
  
Max(0, 3) = 3
  
  
1
  
  
Max(7,-1) = 7
  
  
Max(-1, -1-8) = -1
  
  
-1 + 8 = 7
  
  
Max(0, -1) = -1
  
  
8
  


4.      代码


public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int prevRest = 0;
        int prevHold = - prices[0];
        int prevSell = 0;
        int hold = - prices[0], sell = 0, rest = 0;
        for (int i = 1; i < prices.length; i++) {
            hold = Math.max(prevRest - prices, prevHold);
            sell = prevHold + prices;
            rest = Math.max(prevSell, prevRest);
            prevHold = hold;
            prevSell = sell;
            prevRest = rest;
        }
        return Math.max(sell, rest);
    }

5.      参考
https://discuss.leetcode.com/topic/30680/share-my-dp-solution-by-state-machine-thinking

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表