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

2019-5-22 期三  

动态规划题第五天


167ffc4a5c618d6c328c3b8c88370ef2.png

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


题目解析

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

   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


上一篇: 通过 Let's Encrypt 和七牛云两种方式免费部署 HTTPS 站点

下一篇: 基于 Laravel-admin 的 kindeditor 与 fileupload 拓展