“子序列问题”系列总结，一文读懂（Java实现）

目录

前言

一、最长递增子序列

1.1、dp定义

1.2、递推公式

1.3、初始化

1.4、注意

1.5、解题代码

二、最长连续递增序列

2.1、分析

2.2、解题代码

三、最长重复子数组

3.1、dp定义

3.2、递推公式

3.3、初始化

3.4、解题代码

四、最长公共子序列

4.1、分析

4.2、初始化及遍历顺序

4.3、解题代码

五、不相交的线

5.1、分析

5.2、解题代码

六、最大子数组和

6.1、dp定义

6.2、递推公式

6.3、初始化

6.4、遍历顺序

6.5、解题代码

---

前言

        上一章讲到“买卖股票的最佳时机”系列问题，进行了总结和归纳，本章咱们来看看该如何使用动态规划去解决有关“子序列”这一系列问题！

---

一、最长递增子序列

题目描述：

题目来源：300. 最长递增子序列

1.1、dp定义

分析：

        首先来看一下我们要定义的dp[i]表示的就是题目中所描述的最长子序列长度，进一步，那么这段最长子序列长度是哪一段的长度呢？是以nums[i]为结尾的长度！

dp定义：

dp[i]：以nums[i]为结尾的最长递增子序列的长度。

大多数人的疑惑：

可能很多同学，看到这道题没有思路，就会去看题解，但是看了题解，也没弄清楚dp数组的含义~

一定要注意dp定义中，以nums[i]为结尾的子序列，就是说这段序列中必须包含数字nums[i]，并且，他一定是这段子序列的结尾！

1.2、递推公式

分析：

我们思考的方式因该是：从那些状态才能得出dp[i]？

具体的，如下图：

状态转移方程：

if（nums[j] < nums[i]）

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

1.3、初始化

这里也需要考验你对dp定义的理解了~

dp[i]表示以nums[i]为结尾的最长递增子序列，既然是以xxx为结尾，那么说明长度至少为1！

因此，我们只需要给dp数组都初始化成1即可

1.4、注意

与以往我们做动态规划类的题目不同；

以前我们求出的dp[nums.length - 1]可能就是问题的解了；

但是此题不同的是，dp[nums.length - 1]代表的是以nums[nums.length - 1]为结尾的最长递增子序列，说明这个序列中一定包含nums[nums.length - 1]这个数字，那么，以这个数字为结尾的一定就是最长的递增子序列吗？

当然不是！

例如数组：{1,3,6,7,9,4,10,5,6}，他的最长递增子序列是以6为结尾吗？当然不是，以6为结尾的递增子序列有{1,3,4,5,6}，而已10为结尾的递增子序列有{1,3,6,7,9,10};

dp数组如下：

正好符合咱们的分析，因此我们需要结尾再加个循环遍历dp数组找出最大值，也可以在递推dp时加上一个 result = Math.max(dp[i], result) 找出dp数组中的最大值。

1.5、解题代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        //初始化
        Arrays.fill(dp, 1);//以某一值为结尾，那么长度至少是1
        int result = 1;//保存结果
        //递推
        for(int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {//注意前是递增的序列才被比较添加
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            result = Math.max(dp[i], result);
        }
        return dp[nums.length - 1];
    }
}

---

二、最长连续递增序列

题目描述：

题目来源 ：674. 最长连续递增序列

2.1、分析

本题与 “最长递增子序列” 唯一不同的就是连续，既然要求连续，就只需要对比nums[i]和nums[i - 1]即可，若nums[i] > nums[i - 1]，则“以nums[i]为结尾的最长连续递增序列”就可以由以nums[i - 1]为结尾的最长连续递增序列 + 1”得到；

Ps：本题结合着“最长递增子序列”分析，会更加容易理解；

2.2、解题代码

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 1;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i - 1] < nums[i]) {
                dp[i] = dp[i - 1] + 1;
            }
            if(dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
}

---

三、最长重复子数组

题目描述：

题目来源：718. 最长重复子数组

3.1、dp定义

分析：

想要对比着两个数组去表示状态，那么我们可以用一个二维的数组去表示~

dp[i][j]为了对应最终的解，就表示最长重复子数组的长度了，那么可以如下这样定义；

dp定义：

        dp[i][j]：以 nums1 的第 i - 1 个数字为结尾，以 nums2 的第 j - 1 个数字为结尾，最长重复子数组的长度。

为什么定义成以第i - 1个数字为结尾，而不是以第i个数字为结尾？

这样做是为了减少计算量，怎么就能减少计算量了？

如果我们这样去定义，那么dp[i][0]和dp[0][j]就是没有意义的，因为dp[i][0]表示“以nums1的第i - 1个数字为结尾，以nums2的第 -1 个数字为结尾”，数组下标是不可能为负数的，因此就是没有意义的，再对他初始化的时候，就可以直接初始化成零，因为对比着两个数组，只有两数组数字相同的时候才进行 + 1的操作（+1这里如果不理解，说明“最长递增子序列这道题”你还是没把握住，建议再回去看看那道题）

但是如果我们定义成以i为结尾，初始化的时候nums[i][0]和nums[0][j]该怎么初始化？dp[i][0]就是“nums1以nums1[i]为结尾，nums2以nums2[0]为结尾的最长子数组”，那么我们就需要揪住nums2[0]这个元素去遍历nums1这个数组，去统计相同的元素，同理，nums[0][j]也是如此！

建议：像这类的问题都建议定义成“以i - 1为结尾”，减少不必要的计算！

3.2、递推公式

分析：

dp[i][j]可以由哪些状态得来呢？

当 nums1[i - 1] == nums[j - 1] 时（为什么是 i - 1 前面已经讲过了），是可以由 dp[i - 1][j - 1] + 1 得到dp[i][j]，这时候你可能要问，“为什么不是 dp[i - 1][j] + 1 或者 dp[i][j - 1] + 1 得来的呢？”

原因如下图：

更深入的理解如下：

因为每一次比较都是一对字符进行比较，那么 +1 操作就表示这一对字符相同，所以才 +1 ，而要得到dp[i][j]这个状态，就需要i和j都向前跨越一个字符，站在这个视角，再比较i,j这对字符，若这对字符相同，就+1得到dp[i][j]。

递推公式：

if(nums1[i - 1] == nums2[j - 1]) 

dp[i][j] = dp[i - 1][j - 1] + 1；

3.3、初始化

全都是化成即可，dp[i][0]和dp[j][0]为什么初始化成0，dp定义中讲过了，其余的为什么初始化成0，是因为在递推公式的递推下，初始化的内容都会被覆盖，也就是说，其余的初始化成多少都可以；

3.4、解题代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++) {
            for(int j = 1; j <= nums2.length; j++) {
                if(nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if(result < dp[i][j]) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
}

---

四、最长公共子序列

题目描述：

题目来源：1143. 最长公共子序列

4.1、分析

这道题和 “最长重复子数组” 很相似，不同的是子数组是连续的，而子序列可以是不连续的；

那么他们除了转移方程是不一样的，其他的处理都是一样的；

转移方程分析：

当 text1[i] == text2[j] 时，我们可以由上一个状态dp[i - 1][j - 1] + 1推出来，也就是由“以text1第 i - 2 个字符和以text2第就 j - 2 个字符的最长公共子序列加一”即可得到dp[i][j]；

为什么是i - 1, j - 1呢？

因为每一次比较都是一对字符进行比较，那么 +1 操作就表示这一对字符相同，所以才 +1 ，而要得到dp[i][j]这个状态，就需要i和j都向前跨越一个字符，站在这个视角，再比较i,j这对字符，若这对字符相同，就+1得到dp[i][j]。

当 text1[i] != text2[j] 时呢？dp[i][j]就等于 max(dp[i - 1][j], dp[i][j - 1])，原因如下图：

转移方程：

if(text1.charAt(i - 1) == text2.charAt(j - 1)) 

        dp[i][j] = dp[i - 1][j - 1] + 1;

else 

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

4.2、初始化及遍历顺序

初始化与“最长重复子数组”一样，忘记了可以在往回翻翻看~

由递推公式所需要的状态可以得出下图：

由上图可知，dp[i, j]可以由这几个位置得出，那么遍历顺序一定是从上到下，从左到右遍历的；

4.3、解题代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        int result = 0;
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                if(dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
}

---

五、不相交的线

题目描述：

题目来源：1035. 不相交的线

5.1、分析

        如果你刚刷完上一题“最长公共子序列”，再去深入思考一下这道题，“线不能相交”也就表明序列是有序的，实际上就是在求公共子序列，几乎是一模一样，只是套了一个壳子~

如果有不理解的地方，建议再多去理解一下上面的求“最长公共子序列”问题！

5.2、解题代码

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        int result = 0;
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                if(dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
}

---

六、最大子数组和

题目描述：

题目来源：53. 最大子数组和 

6.1、dp定义

dp[i]表示以nums[i]为结尾的，最长连续子数组的和；（不理解的可以看看前面讲到的题，分析过很多遍了）

6.2、递推公式

分析：

        如何才能得到dp[i]呢？其实就是两种状态，一种是延续之前的状态（之前累加过的数字），加上当前数字，也就是dp[i - 1] + nums[i]；还有一种就是重新进行累加，以当前数字的位置为起始位置，也就是nums[i]，我们只需要得出最大的数字即可，也就是看是否需要延续之前累加好的和，再加上当前数字；

递推公式：

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

6.3、初始化

分析：

        从递推公式中可以看出，要得到dp[i]，需要知道dp[i - 1]，那么一直推到根源就是需要知道dp[0]，其他的值都可以根据dp[0]可以推导出来；

        dp[0]表示以nums[0]为结尾的，最大子数组和，也就是nums[0]；

初始化：

dp[0] = nums[0]；

6.4、遍历顺序

        有递推公式可以知道，要得到dp[i]，需要知道dp[i - 1]，也就是一个顺序遍历即可；另外，dp[nums.length - 1]并不是真正的结果，具体请看“最长递增子序列”这道题中的1.4注意；

6.5、解题代码

class Solution {
    //最大子数组和(动态规划)
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int result = nums[0];
        for(int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if(result < dp[i]) {
                result = dp[i];
            }
        }
        return result;
    }
}

---