内容简介:动态规划题第四天
2 0 1 9 -5 -21 星 期二 开 始 吧
动态规划题第四天
题 目 描 述
给这是一道买卖彩票的扩展题,之前两个版本再前面的文章,这道题指定我们可以 买卖两次,但是我在购买前首先得保证我手上没有股票。求最大的利润。
题目解析
这道题又比之前的题目难,不过分析还是一样的,我们还是先来进行定义状态和递推的操作。
我们根本就不知道前面的状态,是持有股票还是已经卖了,我们也不知道当前交易的次数是否达到了两次,所以这里单单定义一个一维数组是不够的。
然后分情况,第i天第k次都用两种情况持有股票和没有。最后再把思路转换成实现代码。
/** * @param Integer[] $prices * @return Integer */ function maxProfit($prices) { $res=0; $dp[0][0][0]=0; $dp[0][0][1]= -$prices[0]; $dp[0][1][0]= -$prices[0]; $dp[0][1][1]= -$prices[0]; $dp[0][2][0]=0; for($i=1;$i<count($prices);$i++){ $dp[$i][0][0]=$dp[$i-1][0][0]; $dp[$i][0][1]=max($dp[$i-1][0][1],$dp[$i-1][0][0]-$prices[$i]); $dp[$i][1][0]=max($dp[$i-1][1][0],$dp[$i-1][0][1]+$prices[$i]); $dp[$i][1][1]=max($dp[$i-1][1][0]-$prices[$i],$dp[$i-1][1][1]); $dp[$i][2][0]=max($dp[$i-1][2][0],$dp[$i-1][1][1]+$prices[$i]); } $length=count($prices)-1; return max($res,$dp[$length][0][0],$dp[$length][1][0],$dp[$length][2][0]); }
Github整理地址: https://github.com/wuqinqiang/leetcode-php
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode动态规划之PHP解析(120. Triangle)
- 解析 :跻身数据科学领域的五条职业规划道路
- Leetcode动态规划之PHP解析(70. Climbing Stairs)
- Leetcode动态规划之PHP解析(72. Edit Distance)
- Leetcode动态规划之PHP解析(152. Maximum Product Subarray)
- Leetcode动态规划之PHP解析(300. Longest Increasing Subsequence)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Programming in Haskell
Graham Hutton / Cambridge University Press / 2007-1-18 / GBP 34.99
Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs. This introduc......一起来看看 《Programming in Haskell》 这本书的介绍吧!