Leetcode动态规划之PHP解析(300. Longest Increasing Subsequence)

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

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

2 0 1 9 -5 -22   期三    

动态规划题第五天

Leetcode动态规划之 <a href='https://www.codercto.com/topics/18749.html'>PHP</a> 解析(300. Longest Increasing Subsequence)

给定一个数组,找出最长增加的子序列。

题目解析

首先他并不是求连续的,只要后面的数比前面的大,那么他就是可以被添加到子序列中的,只是说每次应该加入较小的数字,才能给后面腾出更多的位置。         

DP[i]=max(DP[i],DP[j]+1) j<i
  当前DP[i]的数和$nums[j]<$nums[$i],dp+1的数最比较得出当前最大子序列
/**
     * @param Integer[] $nums
     * @return Integer
     */
    function lengthOfLIS($nums) {
        if(empty($nums)){
            return 0;
        }
        $res=1;
        for($i=0;$i<count($nums);$i++){
            $dp[$i]=1;
            for($j=0;$j<$i;++$j){
                if($nums[$j]<$nums[$i]){
                    $dp[$i]=max($dp[$i],$dp[$j]+1);
                }
                $res=max($res,$dp[$i]);
            }
        }
        return $res;
    }

Github整理地址: https://github.com/wuqinqiang/leetcode-php


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

查看所有标签

猜你喜欢:

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

Google成功的七堂课

Google成功的七堂课

罗耀宗 / 电子工业出版社 / 2005-7 / 28.00元

Google是全球使用人数最多的搜索引擎,在短短几年内,Google从斯坦福大学的实验室,茁壮成长为举世瞩目的IT业超级巨人,他们的成功绝非偶然,尤其是在网络泡沫破灭,行业一片萧条之际,它的崛起更为IT业带来一缕曙光。作者从趋势观察家的角度,以讲座的形式,向读者讲述Google成功的关键因素:破除因循守旧、不断打破常规,核心技术领先、做出了“更好的捕鼠器”,使得Google在搜索技术方面远远超越对......一起来看看 《Google成功的七堂课》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

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

HSV CMYK互换工具