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


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

查看所有标签

猜你喜欢:

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

突破之道

突破之道

(美)基思 R. 麦克法兰(Keith R. McFarland) / 江南、江维 / 机械工业出版社 / 2017-4 / 49.00

《从优秀到卓越》前传。 深入调查7000多家公司、1500多名关键管理人员,总结提炼出6大突破式发展策略。 解析创业成功后的公司如何腾飞,以几何速度增长,突破10亿关口。 阐述为什么创始人自己才是企业实现突破的最大障碍。一起来看看 《突破之道》 这本书的介绍吧!

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

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具