动态规划-子序列问题（最长递增子序列、最长连续递增序列。最长重复子数组。最长公共子序列、不相交的线、最大子数组和）

超、凢脫俗 2023-09-25 21:17 61阅读 0赞

#### 文章目录 ####

*  1. 最长递增子序列
 *   *   *  思路：
         *  代码：
 *  2. 最长连续递增序列
 *   *   *  思路：
         *  代码：
 *  3. 最长重复子数组
 *   *   *  思路：
         *  代码：
 *  4. 最长公共子序列
 *   *   *  思路：
         *  代码：
 *  5. 不相交的线
 *   *   *  思路：
         *  代码：
 *  6. 最大子数组和
 *   *   *  思路：
         *  代码：

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

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

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

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。

**示例 1：**

> 输入：nums = \[10,9,2,5,3,7,101,18\]  
> 输出：4  
> 解释：最长递增子序列是 \[2,3,7,101\]，因此长度为 4 。

**示例 2：**

> 输入：nums = \[0,1,0,3,2,3\]  
> 输出：4

**示例 3：**

> 输入：nums = \[7,7,7,7,7,7,7\]  
> 输出：1

**提示：**

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

**进阶：**

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

#### 思路： ####

子序列问题是动态规划解决的经典问题，当前下标 i 的递增子序列长度，是和 i 之前的下标 j 的子序列长度有关系的。

**下面进行动态五部曲分析**

1.  状态定义：dp\[i\] 表示 i 之前包括 i 的以 nums\[i\] 结尾的最长递增子序列的长度
2.  状态转移：if(nums\[i\] > nums\[j\]) dp\[i\] = max(dp\[i\], dp\[j\] + 1)
    
    位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 +1 的最大值。这里不是要 dp\[i\] 与 dp\[j\] + 1 进行比较，而是我们要取 dp\[j\] + 1的最大值。
3.  初始化：每个 i，对应的 dp\[i\] （即最长递增子序列）起始大小至少都是 1
4.  遍历顺序：dp\[i\] 是从 0 到 i -1 各个位置的最长递增子序列推导而来，那么遍历 i 一定是从前向后遍历。j 其实就是遍历 0 到 i-1，这个从前到后或从后到前都是可以的。只要把 0 到 i-1 的元素都遍历完就行。
5.  返回值：这个最长的子序列长度，可能是 dp\[i\] 的任意位置，所以，遍历 dp\[i\] 找里面的最大值

#### 代码： ####

class Solution {
        
        /**
        1. 状态定义：dp[i] 表示；以 nums[i] 为结尾的最长递增子序列的长度。
        2. 状态转移：dp[i] = max(dp[j]+1,dp[i]) 
        3. 初始化：dp[0] = 1
        4. 遍历顺序：从小到大
        5. 返回值：
         */
        public int lengthOfLIS(int[] nums) {
        
            if(nums.length == 1) {
        
                return 1;
            }
            int[] dp = new int[nums.length];
            dp[0] = 1;
            int result = 0;
            for(int i = 0; i < dp.length; i++) {
        
                dp[i] = 1;
            }
            // 遍历 dp 数组
            for(int i = 1; i < nums.length; i++) {
        
                // 这里遍历 i 之前的元素 j，是因为下标为 j 的元素，只要 nums[i] > nums[j] 说明是递增的，那么最长递增子序列长度+1（只要比较后大于就长度加一，因为题中说的可以删除元素，来得到子序列）
                for(int j = 0; j < i; j++) {
        
                    if(nums[i] > nums[j]) {
        
                       dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                }
                if(dp[i] > result) result = dp[i]; 
            }
            return result;
        }
    }

## 2. 最长连续递增序列 ##

**题目链接：**[674. 最长连续递增序列 - 力扣（LeetCode）][674. _ - _LeetCode]

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums\[i\] < nums\[i + 1\] ，那么子序列 \[nums\[l\], nums\[l + 1\], …, nums\[r - 1\], nums\[r\]\] 就是连续递增子序列。

**示例 1：**

> 输入：nums = \[1,3,5,4,7\]  
> 输出：3  
> 解释：最长连续递增序列是 \[1,3,5\], 长度为3。  
> 尽管 \[1,3,5,7\] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

**示例 2：**

> 输入：nums = \[2,2,2,2,2\]  
> 输出：1  
> 解释：最长连续递增序列是 \[2\], 长度为1。

**提示：**

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

#### 思路： ####

上一题中的特点是**求最长递增子序列长度**，只要满足后面后面元素大于前面元素就可以，不**要求子序列必须是连续的**。所以要两层 for 一层遍历 dp 数组，一层遍历 nums 数组元素，找到递增的元素。

而本道题中的特点**是求最长递增子序列长度，但子序列必须是连续的**

**下面进行动归五部曲分析**

1.  状态定义：dp\[i\] 表示：以下标 i 为结尾的连续递增的子序列长度为 dp\[i\]
    
    这里的定义，一定是以下标 i 为结尾，但并不是说子序列的起始位置是 0.
2.  状态转移：因为是要求子序列必须连续，所以当 nums\[i\] > nums\[i-1\] 时，以 i 为结尾的连续递增子序列长度 = 以 i -1 为结尾的连续递增的子序列长度 + 1
    
    即 dp\[i\] = dp\[i-1\] + 1 （这里和上一题不同，因为本道题是必须连续，所以满足条件后才能长度加一）
3.  初始化：dp\[i\] = 1
4.  遍历顺序：从后向前
5.  返回值：找到 dp 数组中最大的值进行返回

#### 代码： ####

/**
        1. 状态定义：以下标 i 为结尾的连续递增的子序列长度为 dp[i]
        2. 状态转移：当 nums[i] > nums[i-1] 时,dp[i] = dp[i-1] + 1
        3. 初始化；dp[i] = 1
        4. 遍历顺序：从后向前
        5. 返回值：找到 dp 数组中最大的值进行返回
         */
        public int findLengthOfLCIS(int[] nums) {
        
            int n = nums.length;
            if(n == 1) return 1;
            int[] dp = new int[n];
            int result = 0;
            // 初始化
            for(int i = 0; i < n; i++) {
        
                dp[i] = 1;
            }
            // 遍历
            for(int i = 1; i < n; i++) {
        
                if(nums[i] > nums[i-1]) {
        
                    dp[i] = dp[i-1]+1;
                }
                if(result < dp[i]) result = dp[i];
            }
            return result;
        }

## 3. 最长重复子数组 ##

**题目链接：**[718. 最长重复子数组 - 力扣（LeetCode）][718. _ - _LeetCode]

给两个整数数组 nums1 和 nums2 ，返回 两个数组中公共的 、长度最长的子数组的长度 。

**示例 1：**

> 输入：nums1 = \[1,2,3,2,1\], nums2 = \[3,2,1,4,7\]  
> 输出：3  
> 解释：长度最长的公共子数组是 \[3,2,1\] 。

**示例 2：**

> 输入：nums1 = \[0,0,0,0,0\], nums2 = \[0,0,0,0,0\]  
> 输出：5

**提示：**

*  1 <= nums1.length, nums2.length <= 1000
 *  0 <= nums1\[i\], nums2\[i\] <= 100

#### 思路： ####

本题是求两个数组中最长重复子数组，可以用动态规划来解决这道题目，首先要明确，可以用二维数组来记录两个字符串的所有比较情况。

**下面进行动归五部曲分析**

1.  状态定义：dp\[i\] \[j\] 表示：以下标 i - 1 为结尾的 A，和以下标 j - 1 为结尾的 B，它的最长重复子树组长度为 dp\[i\] \[j\]（以下标 i - 1 为结尾的 A，也就是以 A\[i-1\] 为结尾的字符串）
2.  状态转移：if(A\[i-1\] == B\[j-1\]) dp\[i\] \[j\] = dp\[i-1\] \[j-1\] + 1
3.  初始化：由 dp 数组定义分析，dp\[i\] \[0\] 和 dp\[0\] \[j\] 是没有意义的，但是递推公式又要用这个，所以就初始化为 0,。
    
    比如 A\[0\] 如果和 B\[0\] 相同的话，dp\[1\] \[1\] = dp\[0\] \[0\] + 1，只有 dp\[0\] \[0\] 初始化为 0，才符合递推公式逐步累加起来。
4.  遍历顺序：一层遍历 A，一层遍历 B （顺序没要求）
    
    在遍历的时候，用 result 记录长度最长的子数组长度
5.  返回值：result

当然在状态定义时，也可以定义为 以下标 i 为结尾的 A，和以下标 j 为结尾的 B，它的最长重复子数组长度为 dp\[i\] \[j\].

但是这样定义，那么第一行和第一列的初始化就不能为 0 了，如果 nums1\[i\] 与 nums2\[0\] 相同的话，对应的 dp\[i\] \[0\] 就要初始化为 1，因为此时最长重复子数组为 1.

#### 代码： ####

**先写状态定义为 以下标 i 为结尾的 A，和以下标 j 为结尾的 B，它的最长重复子数组长度为 dp\[i\] \[j\].**，这种更好理解，但写法麻烦

public int findLength(int[] nums1, int[] nums2) {
        
            int result = 0;
            int n1 = nums1.length;
            int n2 = nums2.length;
            int[][] dp = new int[n1][n2];
            // 初始化
            for(int i = 0; i < n1; i++) {
        
                if(nums1[i] == nums2[0]) {
        
                    dp[i][0] = 1;
                }
            }
            for(int j = 0; j < n2; j++) {
        
                if(nums2[j] == nums1[0]) {
        
                   dp[0][j] = 1;
                }
            }
            // 遍历
            for(int i = 0; i < n1; i++) {
        
                for(int j = 0; j < n2; j++) {
        
                    if(nums1[i] == nums2[j] && i > 0 && j > 0) {
        
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }
                    if(result < dp[i][j]) result = dp[i][j];
                }
            }
            return result;
        }

**以下标 i - 1 为结尾的 A，和以下标 j - 1 为结尾的 B，它的最长重复子树组长度为 dp\[i\] \[j\]**

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

## 4. 最长公共子序列 ##

**题目链接：**[1143. 最长公共子序列 - 力扣（LeetCode）][1143. _ - _LeetCode]

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。  
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

**示例 1：**

> 输入：text1 = “abcde”, text2 = “ace”  
> 输出：3  
> 解释：最长公共子序列是 “ace” ，它的长度为 3 。

**示例 2：**

> 输入：text1 = “abc”, text2 = “abc”  
> 输出：3  
> 解释：最长公共子序列是 “abc” ，它的长度为 3 。

**示例 3：**

> 输入：text1 = “abc”, text2 = “def”  
> 输出：0  
> 解释：两个字符串没有公共子序列，返回 0 。

**提示：**

*  1 <= text1.length, text2.length <= 1000
 *  text1 和 text2 仅由小写英文字符组成。

#### 思路： ####

本道题和上一题的区别就是，不要求是连续的公共子序列了，但相对顺序还是不能变的。

**下面还是用动归五部曲分析**

1.  状态定义：dp\[i\] \[j\] 表示：长度为 \[0, i-1\] 的字符串 text1 与长度为 \[0, j-1\] 的字符串 text2 的最长公共子序列为 dp\[i\] \[j\]。
    
    这里也可以定义长度为 \[0, i\] 的字符串 text1，和长度为 \[0, j\] 的字符串 text2，但是不建议这样定义，如果这样定义的话 dp\[0\] \[j\] 和 dp\[i\] \[0\] 就必须满足 nums1\[i\] == nums2\[0\] ， nums1\[0\] == nums2\[j\] 时初始化为 1，这样比较麻烦，而定义成 i-1 和 j-1 不用额外判断初始化是因为，在递推公式中就可以初始化。
2.  状态转移：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\] \[j-1\],dp\[i-1\] \[j\]); // 取这两种情况中最大的。
    
    \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rsiZVTtD-1680431895953)(C:\\Users\\28463\\AppData\\Roaming\\Typora\\typora-user-images\\1680078717079.png)\]
3.  初始化：都初始化为 0
    
    比如 dp\[i\] \[0\] 的初始化，test1\[0,i-1\] 和空串的最长公共子序列为 0，所以 dp\[i\] \[0\] = 0,同理 dp\[0\] \[j\] 也是 0，其他的下标随着递推公式逐步覆盖。所以这里初始化什么都可以，为了方便起见就统一初始化为 0。
4.  遍历顺序：可以由上面的图看出来，遍历要从小到大
5.  返回值：因为每次递推都是把最大给 dp\[i\] \[j\] ，所以要返回递推到最后的值，dp\[test1.length()\] \[test2.length()\]

#### 代码： ####

/**
        1. 状态定义：以 (0,i-1] 为结尾的 text1，和 (0,j-1] 为结尾的 text2 的最长公共子序列为 dp[i][j]
        2. 状态转移：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][j-1],dp[i-1][j]); 
        3. 初始化：dp[i][0] = 0, dp[j][0] = 0 （因为状态定义时，取的是 -1）
        4. 遍历顺序： 从小到大
        5. 返回值：dp[text1.length()][text2.length()]
         */
        public int longestCommonSubsequence(String text1, String text2) {
        
            int n1 = text1.length();
            int n2 = text2.length();
            int[][] dp = new int[n1+1][n2+1];
            for(int i = 1; i <= n1; i++) {
        
                for(int j = 1; j <= n2; 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][j-1],dp[i-1][j]);
                    }
                }
            }
            return dp[n1][n2];
        }

## 5. 不相交的线 ##

**题目链接：**[1035. 不相交的线 - 力扣（LeetCode）][1035. _ - _LeetCode]

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1\[i\] 和 nums2\[j\] 的直线，这些直线需要同时满足满足：

nums1\[i\] == nums2\[j\]  
且绘制的直线不与任何其他连线（非水平线）相交。  
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

**示例 1：**

> 输入：nums1 = \[1,4,2\], nums2 = \[1,2,4\]  
> 输出：2  
> 解释：可以画出两条不交叉的线，如上图所示。  
> 但无法画出第三条不相交的直线，因为从 nums1\[1\]=4 到 nums2\[2\]=4 的直线将与从 nums1\[2\]=2 到 nums2\[1\]=2 的直线相交。

**示例 2：**

> 输入：nums1 = \[2,5,1,2,5\], nums2 = \[10,5,2,1,5,2\]  
> 输出：3

**示例 3：**

> 输入：nums1 = \[1,3,7,1,7,5\], nums2 = \[1,9,2,5,1\]  
> 输出：2

**提示：**

> 1 <= nums1.length, nums2.length <= 500  
> 1 <= nums1\[i\], nums2\[j\] <= 2000

#### 思路： ####

分析一下题目，要通过直线连接两个数字 nums1\[i\] 和 nums2\[j\]，第一个条件是 nums1\[i\] == nums2\[j\] ，第二个条件是直线不能相交，意思就是要在 nums1 中找到一个与 nums2 相同的 **子序列**，并且这个子序列\*\*不能改变相对顺序，\*\*只要相对顺序不改变，那么直线就不会相交。

所以，这道题虽然说的是求绘制的最大连线数，本质上还是求两个字符串的最长公共子序列的长度。这就是上一题了。

#### 代码： ####

public int maxUncrossedLines(int[] nums1, int[] nums2) {
        
            int n1 = nums1.length;
            int n2 = nums2.length;
            int[][] dp = new int[n1+1][n2+1];
            for(int i = 1; i <= n1; i++) {
        
                for(int j = 1; j <= n2; 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]);
                    }
                }
            }
            return dp[n1][n2];
        }

## 6. 最大子数组和 ##

**题目链接：**[53. 最大子数组和 - 力扣（LeetCode）][53. _ - _LeetCode]

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

**示例 1：**

> 输入：nums = \[-2,1,-3,4,-1,2,1,-5,4\]  
> 输出：6  
> 解释：连续子数组 \[4,-1,2,1\] 的和最大，为 6 。

**示例 2：**

> 输入：nums = \[1\]  
> 输出：1

**示例 3：**

> 输入：nums = \[5,4,-1,7,8\]  
> 输出：23

**提示：**

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

**进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。**

#### 思路： ####

题中是具有最大和的连续子数组，这个既然是求和那么是后一个状态依靠前一个状态，所以要用动态规划

**下面进行动归五部曲分析**

1.  状态定义：dp\[i\] 表示：包括下标 i （以 nums\[i\] 为结尾）的最大连续子序列和为 dp\[i\]。
2.  状态转移：dp\[i\] = Math.max(dp\[i-1\]+nums\[i\],nums\[i\])
    
    dp\[i-1\] + nums\[i\] 也就是当 nums\[i\] 加入当前连续子序列和中
    
    nums\[i\] 表示从头开始计算当前连续子序列和
    
    这两种情况取其最大的
3.  初始化：根据状态转移方程可以分析出 dp\[i\] 依赖于 dp\[i-1\]，所以 dp\[0\] 就是基础，根据状态定义得出 dp\[0\] = nums\[0\]
4.  遍历顺序：从小到大
5.  返回值：取其最大的 dp

#### 代码： ####

/**
        1. 状态定义：以 i 为结尾(nums[i]) 的最大连续子数组和为 dp[i]
        2. 状态转移：dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
        3. 初始化：dp[0] = nums[0]
        4. 遍历顺序：从小到大
        5. 返回值：取所有 dp 中最大的
         */
        public int maxSubArray(int[] nums) {
        
            int n = nums.length;
            int[] dp = new int[n];
            int result = nums[0];
            dp[0] = nums[0];
            for(int i = 1; i < n; i++) {
        
                dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
                if(result < dp[i]) {
        
                    result = dp[i];
                }
            }
            return result;
        }

[300. _ - _LeetCode]: https://leetcode.cn/problems/longest-increasing-subsequence/
[674. _ - _LeetCode]: https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
[718. _ - _LeetCode]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
[1143. _ - _LeetCode]: https://leetcode.cn/problems/longest-common-subsequence/
[1035. _ - _LeetCode]: https://leetcode.cn/problems/uncrossed-lines/
[53. _ - _LeetCode]: https://leetcode.cn/problems/maximum-subarray/