内容简介:动态规划题第四天
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)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。