[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1077|回复: 0
收起左侧

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

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

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

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

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

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 18:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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