力扣300-最长递增子序列（Java详细题解）

题目链接：300. 最长递增子序列 - 力扣（LeetCode）

前情提要：

本题是子序列问题的开始篇，接下来我将更新子序列篇章的dp问题。

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

本题题目描述要求我们对数组中找到最长的递增子序列，子序列可以是不连续的元素。

话不多说，直接用dp五部曲系统分析一下。

1.确定dp数组和i下标的含义。

本题要求最长严格递增子序列的长度，所以dp[i]定义为以下标i结尾的数组最长递增子序列的长度。

2.确定递推公式。

本题是求的递增的子序列，所以肯定是要让用nums[j] 来遍历nums[i]。

如果nums[i] > nums[j]才是递增的，就可以添加到我们的结果集中。

那么怎么才能得出本数组的最长递增长序列呢？

其实有点像力扣139的单词拆分，如果j到i这段是递增（nums[i] > nums[j])的，那么i的最长递增子序列就为dp[j] + 1。

就为之前以j为结尾的最长递增子序列加上nuns[i]这个元素，所以就为dp[j] + 1。

因为要求最长递增长序列，所以需要对dp[i] 取一个最大。

dp[i] = Math.max(dp[j] + 1,dp[i]);

3.dp初始化。

由dp数组可以看出，dp[i]是指以下标i结尾的数组最长递增子序列的长度。所以每个dp[i]的最长递增子序列都最少为1。

那么我们就将整个数组都初始化为1。

4.确定dp的遍历顺序。

由递推公式可以看出 dp[i] = Math.max(dp[j] + 1,dp[i]);，而dp[j]又是要遍历dp[i] ，所以遍历顺序只能是从前往后遍历。

5.如果没有ac打印dp数组 利于debug。

最终代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp数组定义 以nums[i]为结尾的最长子序列的长度
        //在这里要对nums长度为1进行特判，因为如果长度为1就不会进入循环 而我的result 是初始化为0 所以会为0
        //但是如果nums长度为1 他的最长递增子序列就是他本身 所以长度为1 你初始化result = 1也可以
        if(nums.length == 1)return 1;
        //该题关键就是递推公式 
        int [] dp = new int [nums.length + 1];
        int result = 0;
        Arrays.fill(dp,1);
        for(int i = 1;i < nums.length;i ++){
            for(int j = 0;j < i;j ++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
            //收集结果的地方 可能不是最后一个位置 可能是任意位置 所以要对任意位置结尾的最长子序列的长度取一个最值
            result = Math.max(result,dp[i]);
        }
        return result;

    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！