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

2019-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