300. 最长递增子序列（动态规划）

﹏ヽ暗。殇╰゛Y 2023-10-05 18:23 12阅读 0赞

#### 300. 最长递增子序列 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
提示：

*  1 <= nums.length <= 2500
 *  \-104 <= nums\[i\] <= 104

进阶：

*  你可以设计时间复杂度为 O(n2) 的解决方案吗？**本解法已达到**
 *  你能将算法的时间复杂度降低到 O(n log(n)) 吗?**用二分搜索解法**

## 解题思路 ##

首先我们要规定以下`dp[i]`代表什么含义：**dp\[i\]存放的是：以nums\[i\]结尾的最长递增子序列的长度**。

然后根据这个定义我们可以推出base case: `dp[i]`的初始值都要为1。因为以nums\[i\]结尾的最长递增子序列最起码要包含 它自己。

由此可以得出算法的过程就是从`dp[0]`一直演算到`dp[i]`。那么如何正确的求出dp\[i\]呢？  
假设有一个数组`[1,4,3,4,2,3]`，我们已经知道`dp[0-4]`，求出`dp[5]`。

> 根据之前的dp\[i\]的定义可以知道：现在nums\[5\]=3，我们只需要找到nums\[5\]前面哪些小于3的子序列，然后把3拼接到那个子序列后面，再给那个子序列的长度+1，就可以了。  
> 当然要注意，可能会拼接出来很多种子序列，，我们只要选择其中最长的那个，然后把拼接后子序列的长度作为dp\[5\]的值。

用代码来表示就是下面

for (int j = 0; j < i; j++) {
        
    		if (nums[j] < nums[i]) {
        
    			[i] = Math.max(dp[i], dp[j] + 1);
    		}
     }

让`i=5`就是求出dp\[5\]的值，那么dp\[0-4\]的求解方式一样，只要让i动起来就可以了。所以稍微改一下代码

for (int i = 0; i < N; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    if (nums[j] < nums[i]) {
        
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }

到这里这题就差不多了。

## 代码 ##

class Solution {
        
      public int lengthOfLIS(int[] nums) {
        
            if (nums.length < 0) {
        
                return -1;
            }
            if (nums.length == 0) {
        
                return 0;
            }
            int N = nums.length;
            //dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度
            int[] dp = new int[N];
    
    
            //base case：将dp[]都初始化为1
            Arrays.fill(dp, 1);
    
            for (int i = 0; i < N; i++) {
        //i=N-1就是dp[]的最后一个元素了，原为dp[]的长度和nums[]的相同
                for (int j = 0; j < i; j++) {
        
                    if (nums[j] < nums[i]) {
        //找到比当前值小的，并且在当前值之前出现的值
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
    
            int res = 0;
            //来遍历一次经过整理的dp[]，找出最大值
            for (int i = 0; i < dp.length; i++) {
        
                res = Math.max(res, dp[i]);
            }
    
            return res;
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202101251737371.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70