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

2019-5-22 星期三  开始吧

动态规划题第五天

题目描述

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

题目解析

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

   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