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

文章目录

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

1. 最长递增子序列

题目链接：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）

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

连续递增的子序列 可以由两个下标 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）

给两个整数数组 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）

给定两个字符串 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）

在两条独立的水平线上按给定的顺序写下 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）

给你一个整数数组 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;
    }