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

约定不等于承诺〃 2023-09-23 22:52 30阅读 0赞

**目录**

前言

一、最长递增子序列

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、解题代码

--------------------

# 前言 #

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

--------------------

# 一、最长递增子序列 #

> 题目描述：

![6c4641b57f434ce183e21ad30f457caa.png][]

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

## 1.1、dp定义 ##

> 分析：

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

> dp定义：

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

> 大多数人的疑惑：

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

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

## 1.2、递推公式 ##

> 分析：

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

具体的，如下图：

![cc50cf9c31d14021a1b7d33baed3f5fa.png][]

> 状态转移方程：

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数组如下：

![9c2824f349c04e11908a6c3c09cddf4d.png][]

正好符合咱们的分析，因此我们需要结尾再加个循环遍历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];
        }
    }

--------------------

# 二、最长连续递增序列 #

> 题目描述：

![d27ef9eb221e460d811e8fcf9ad3d27e.png][]

题目来源 ：[674. 最长连续递增序列][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;
        }
    }

--------------------

# 三、最长重复子数组 #

> 题目描述：

![147b355c2e384552a962cc6b84053624.png][]

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

## 3.1、dp定义 ##

> 分析：

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

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

> dp定义：

dp\[i\]\[j\]：以nums1的第i - 1个数字为结尾，以nums2的第i - 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 得来的呢？”

原因如下图：

![3d9ecc84c8af43da96e2ecba80f4a2db.png][]

更深入的理解如下：

**因为每一次比较都是一对字符进行比较，那么 +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;
        }
    }

--------------------

# 四、最长公共子序列 #

> 题目描述：

![88f55bfd71a14106bed9d45909a22dee.png][]

题目来源：[1143. 最长公共子序列][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呢？**

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

![da89107a41f749a9bafb1f28e9c22ee7.png][]

> 转移方程：

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、初始化及遍历顺序 ##

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

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

![99b093dca6994aebb0707d898bdf4acb.png][]

由上图可知，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;
        }
    }

--------------------

# 五、不相交的线 #

> 题目描述：

![e4cf0c0fa3b14f089a02e8655cba7c2a.png][]

![c1bfc380b8ea4f8085d3e0691e2b1cdd.png][]

题目来源：[1035. 不相交的线][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;
        }
    }

--------------------

# 六、最大子数组和 #

> 题目描述：

![666700def31c4170b0e1ab813ff7a7a6.png][]

题目来源：[53. 最大子数组和][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;
        }
    }

--------------------

![d0a649b1e0de4f7482cbb7eca455a4e5.gif][]

[6c4641b57f434ce183e21ad30f457caa.png]: https://img-blog.csdnimg.cn/6c4641b57f434ce183e21ad30f457caa.png
[300.]: https://leetcode.cn/problems/longest-increasing-subsequence/
[cc50cf9c31d14021a1b7d33baed3f5fa.png]: https://img-blog.csdnimg.cn/cc50cf9c31d14021a1b7d33baed3f5fa.png
[9c2824f349c04e11908a6c3c09cddf4d.png]: https://img-blog.csdnimg.cn/9c2824f349c04e11908a6c3c09cddf4d.png
[d27ef9eb221e460d811e8fcf9ad3d27e.png]: https://img-blog.csdnimg.cn/d27ef9eb221e460d811e8fcf9ad3d27e.png
[674.]: https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
[147b355c2e384552a962cc6b84053624.png]: https://img-blog.csdnimg.cn/147b355c2e384552a962cc6b84053624.png
[718.]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
[3d9ecc84c8af43da96e2ecba80f4a2db.png]: https://img-blog.csdnimg.cn/3d9ecc84c8af43da96e2ecba80f4a2db.png
[88f55bfd71a14106bed9d45909a22dee.png]: https://img-blog.csdnimg.cn/88f55bfd71a14106bed9d45909a22dee.png
[1143.]: https://leetcode.cn/problems/longest-common-subsequence/
[da89107a41f749a9bafb1f28e9c22ee7.png]: https://img-blog.csdnimg.cn/da89107a41f749a9bafb1f28e9c22ee7.png
[99b093dca6994aebb0707d898bdf4acb.png]: https://img-blog.csdnimg.cn/99b093dca6994aebb0707d898bdf4acb.png
[e4cf0c0fa3b14f089a02e8655cba7c2a.png]: https://img-blog.csdnimg.cn/e4cf0c0fa3b14f089a02e8655cba7c2a.png
[c1bfc380b8ea4f8085d3e0691e2b1cdd.png]: https://img-blog.csdnimg.cn/c1bfc380b8ea4f8085d3e0691e2b1cdd.png
[1035.]: https://leetcode.cn/problems/uncrossed-lines/
[666700def31c4170b0e1ab813ff7a7a6.png]: https://img-blog.csdnimg.cn/666700def31c4170b0e1ab813ff7a7a6.png
[53.]: https://leetcode.cn/problems/maximum-subarray/
[d0a649b1e0de4f7482cbb7eca455a4e5.gif]: https://img-blog.csdnimg.cn/d0a649b1e0de4f7482cbb7eca455a4e5.gif