Leetcode动态规划之PHP解析(123. Best Time to Buy and Sell Stock III)


2019-5-21 期二  


动态规划题第四天

48090450e388a5f8ead3bfa3402addec.png


给这是一道买卖彩票的扩展题,之前两个版本再前面的文章,这道题指定我们可以 买卖两次,但是我在购买前首先得保证我手上没有股票。求最大的利润。


题目解析


这道题又比之前的题目难,不过分析还是一样的,我们还是先来进行定义状态和递推的操作。

b834cd3017b69927a0c19439023c2369.png

我们根本就不知道前面的状态,是持有股票还是已经卖了,我们也不知道当前交易的次数是否达到了两次,所以这里单单定义一个一维数组是不够的。

28a02d5042b1585f9ca1a719c047f681.png

然后分情况,第i天第k次都用两种情况持有股票和没有。最后再把思路转换成实现代码。

6b5322de08a068404557597b5233e861.png

   /**
     * @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


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D67 485. Max Consecutive Ones

>> 下一篇: Leetcode PHP题解--D68 283. Move Zeroes