星尘

动态规划总结-子序列

发表于 更新于 分类于 ，

最长递增子序列

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

  • dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
  • 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值, 所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
  • 每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1
  • dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        dp = [1] * len(nums)
        result = 1
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            result = max(result, dp[i]) #取长的子序列
        return result

输入：[0,1,0,3,2]，dp数组的变化如下

最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。连续递增的子序列 可以由两个下标 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

  • dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]
  • 如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1。即：dp[i] = dp[i - 1] + 1
  • 注意这里就体现出和 最长上升子序列 的区别，因为本题要求连续递增子序列，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。既然不用j了，那么也不用两层for循环，本题一层for循环就行，比较nums[i] 和 nums[i - 1]
  • 以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。所以dp[i]应该初始1
  • 从递推公式上可以看出， dp[i + 1]依赖dp[i]，所以一定是从前向后遍历
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]: #连续记录
                dp[i] = dp[i-1] + 1
            result = max(result, dp[i])
        return result

输入nums = [1,3,5,4,7]为例，dp数组状态如下

最长重复子数组

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

示例, 输入：A: [1,2,3,2,1], B: [3,2,1,4,7], 输出：3, 解释：长度最长的公共子数组是 [3, 2, 1] 。

  • dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
  • dp[i][j]的定义也就决定着，我们在遍历dp[i][j]的时候i 和 j都要从1开始
  • 根据 dp[i][j] 的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1
  • 根据dp[i][j]的定义，dp[i][0]和dp[0][j]其实都是没有意义的。但dp[i][0]和dp[0][j]要初始值，为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1, 所以dp[i][0]和dp[0][j]初始化为0
  • 对于遍历顺序，外循环遍历A，内层循环遍历B，外循环遍历B，内层循环遍历A 都可以
  • 同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来
  • 上面两题是求一个数组的递增子序列和连续递增子序列，都需要判断元素谁大谁小，而且是只有一个数组。而本题是求两个数组的重复子数组。区别在于本题是循环两个数组且判断的是元素是否相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # 创建一个二维数组 dp，用于存储最长公共子数组的长度
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        # 记录最长公共子数组的长度
        result = 0

        # 遍历数组 nums1
        for i in range(1, len(nums1) + 1):
            # 遍历数组 nums2
            for j in range(1, len(nums2) + 1):
                # 如果 nums1[i-1] 和 nums2[j-1] 相等
                if nums1[i - 1] == nums2[j - 1]:
                    # 在当前位置上的最长公共子数组长度为前一个位置上的长度加一
                    dp[i][j] = dp[i - 1][j - 1] + 1
                # 更新最长公共子数组的长度
                if dp[i][j] > result:
                    result = dp[i][j]

        # 返回最长公共子数组的长度
        return result

示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下

为什么dp[i][j]不能定义为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度？

如果定义 dp[i][j] 为 以下标i为结尾的A，和以下标j 为结尾的B，那么 第一行和第一列毕竟要进行初始化，如果nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0]就要初始为1， 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话，同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 版本三
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;

        // 要对第一行，第一列经行初始化
        for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;
        for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;

        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                if (nums1[i] == nums2[j] && i > 0 && j > 0) { // 防止 i-1 出现负数
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

也可以从上述的图中看出，不这么定义是为了方便初始化，使得逻辑更简单通用和清晰。这样就不用考虑 nums1[i] 与 nums2[0] 是否相同，也不用考虑 nums2[j] 与 nums1[0] 是否相同，for 循环直接从 1 开始即可。

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。

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

  • 本题和最长重复子数组的区别在于这里不要求是连续的了，但要有相对顺序，即：”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
  • dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。这里定义到 i-1和 j-1 的原因和上面一题一致。
  • text1[i - 1] 与 text2[j - 1]相同
    • text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以 dp[i][j] = dp[i - 1][j - 1] + 1
  • text1[i - 1] 与 text2[j - 1]不相同
    • 那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 创建一个二维数组 dp，用于存储最长公共子序列的长度
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        # 遍历 text1 和 text2，填充 dp 数组
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    # 如果 text1[i-1] 和 text2[j-1] 相等，则当前位置的最长公共子序列长度为左上角位置的值加一
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    # 如果 text1[i-1] 和 text2[j-1] 不相等，则当前位置的最长公共子序列长度为上方或左方的较大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # 返回最长公共子序列的长度
        return dp[len(text1)][len(text2)]

以输入：text1 = “abcde”, text2 = “ace” 为例，dp状态如图

不相交的线

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。以这种方法绘制线条，并返回我们可以绘制的最大连线数。

  • 直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交
  • 本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
  • 那么本题就和上一题最长公共子序列就是一样的了
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0] * (len(B)+1) for _ in range(len(A)+1)]
        for i in range(1, len(A)+1):
            for j in range(1, len(B)+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

最大子序和

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

示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6, 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

  • dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]
  • dp[i]只有两个方向可以推出来
    • dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
    • nums[i]，即：从头开始计算当前连续子序列和
  • 一定是取最大的，所以 dp[i] = max(dp[i - 1] + nums[i], nums[i])

  • 根据dp[i]的定义，很明显dp[0]应为nums[0]

  • 递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历

以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：

1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        result = dp[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i]) #状态转移公式
            result = max(result, dp[i]) #result 保存dp[i]的最大值
        return result