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


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

查看所有标签

猜你喜欢:

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

从问题到程序

从问题到程序

裘宗燕 / 机械工业出版社 / 2005-9-1 / 36.00元

本书以C作为讨论程序设计的语言,讨论了基本程序设计的各方面问题。书中给出程序实例时没有采用常见的提出问题,给出解答,再加些解释的简单三步形式,而是增加了许多问题的分析和讨论,以帮助读者认识程序设计过程的实质,理解从问题到程序的思考过程。书中还尽可能详尽地解释了许多与C语言和程序设计有关的问题。 本书适合作为高等院校计算机及相关专业的教材,也可供其他学习C程序设计语言的读者阅读。一起来看看 《从问题到程序》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

在线进制转换器
在线进制转换器

各进制数互转换器

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

HSV CMYK互换工具