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

栏目: PHP · 发布时间: 5年前

内容简介:动态规划题第四天

2 0 1 9 -5 -21   期二    

动态规划题第四天

Leetcode动态规划之 <a href='https://www.codercto.com/topics/18749.html'>PHP</a> 解析(123. Best Time to Buy and Sell Stock III)

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

题目解析

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

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

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

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

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

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

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Programming in Haskell

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》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具