leetcode(力扣) 718. 最长重复子数组 & 1143. 最长公共子序列 (动态规划)

这三道题思路基本一样，尤其是最后两道，代码都一样，一点不需要改的，所以放一起把。

718. 最长重复子数组

题目描述

给两个整数数组 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.确定dp下标含义：

dp[i][j] 表示数组A到下标i-1，数组B到下标j-1，时的公共最长子数组的长度。

这是力扣上大多数题解这么说的，不过有没有发现，为什么是到i-1 j-1，如果不看题解，自己做的话拿到这道题，dp定义肯定是 数组A到下标i，数组B到下标j，时的公共最长子数组的长度。

所以为啥是这样？后面再说。

2.状态转移公式：

根据上面定义的dp数组含义，很容易想到，dp[i][j]的状态就看前一个nums[i-1] 是不是等于 nums[j-1] 如果等于，则dp[i][j] = dp[i-1][j-1]+1。

偷张图，助于理解。

3.初始化

直接初始化成全0就行，观察推导公式，严格来说，只需要初始化第一行和第一列为0，其余初始化成什么都无所谓。

4.遍历顺序

因为第一行和第一列已经初始化了，所以先遍历行还是列都无所谓。正着来就行了。

所以！！！！！
所以！！！！！
所以！！！！！

为什么在初始化dp数组的时候是：
数组A到下标i-1，数组B到下标j-1，时的公共最长子数组的长度 。（情况一）
而不是：
数组A到下标i，数组B到下标j，时的公共最长子数组的长度 。（情况二）

我看力扣上压根没人说，其实这道题的关键才是在这里，因为拿到手肯定会按情况二去定义。

来看一下如果说定义成情况二会发生什么？

原来的第一行和第一列是没有数字的，因为dp[0][0] 表示 数组A到下标-1？？？？？
显然是没意义的，所以第一行和第一列都初始化成了0.

而情况二的时候，第一行和第一列都是有意义的，所以初始化这里要一点一点去写了。

即：第一行所有数字，如果和第一列第一个数相等，则赋值1，否则为0.
第一列所有数字，如果和第一行第一个数字相等，则赋值1，否则0.

这块看上面那个二维数组的图就秒懂。

		# 初始化第一行。
        for i in range(len(nums1)):
            if nums2[0] == nums1[i]:
                dp[0][i] = 1
                res = 1
        # 初始化第一列
        for i in range(len(nums2)):
            if nums1[0] == nums2[i]:
                dp[i][0] = 1
                res = 1
1
2
3
4
5
6
7
8
9
10

完整代码

dp[i][j] 含义为 数组A到下标i-1，数组B到下标j-1，时的公共最长子数组的长度  。

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j] 表示 两数组均到i-1时的最长公共子数组。


        dp = [[0 for _ in range(len(nums2)+1)] for _ in range(len(nums1)+1)]
        res = 0
        for i in range(1,len(nums1)+1):
            for j in range(1,len(nums2)+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                res = max(res,dp[i][j])

        return res
        
dp含义为：数组A到下标i，数组B到下标j，时的公共最长子数组的长度  。（情况二）
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j] 表示 两数组均到i时的最长公共子数组。
        dp = [[0 for _ in range(len(nums1))] for _ in range(len(nums2))]
        res = 0
        # 初始化第一行。
        for i in range(len(nums1)):
            if nums2[0] == nums1[i]:
                dp[0][i] = 1
                res = 1
        # 初始化第一列
        for i in range(len(nums2)):
            if nums1[0] == nums2[i]:
                dp[i][0] = 1
                res = 1

        for i in range(1,len(nums2)):
            for j in range(1,len(nums1)):
                if nums1[j] == nums2[i]:
                    dp[i][j] = dp[i-1][j-1]+1
                res = max(res,dp[i][j])
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

1143. 最长公共子序列

这道题和上面那一道题其实是类似的。

这里的子序列是可以不连续的，而子数组是需要连续的。

1.dp数组含义
跟上一题相同的地方是dp数组的含义，同样为了方便定义成：dp[i][j] 表示 A字符串到下标为i-1 和 B字符串到下标为 j-1 的公共最长子序列的长度。

跟上一题一样的问题,为啥不定义成下标到 i 。答案也是一样的，因为如果定义成：dp[i][j] 表示 A字符串到下标为i 和 B字符串到下标为 j 的公共最长子序列的长度，那就得初始化第一行和第一列。 定义成i-1，就全初始化成0就行了。

定义成 i 的初始化:

		# 初始化第一行。
        for i in range(len(nums1)):
            if nums2[0] == nums1[i]:
                dp[0][i] = 1
            else:
                dp[0][i] =dp[0][i-1]

        # 初始化第一列
        for i in range(len(nums2)):
            if nums1[0] == nums2[i]:
                dp[i][0] = 1
            else:
                dp[i][0] = dp[i-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13

2.状态转移方程

首先肯定还是得比较 text1[i - 1] 和 text2[j - 1] 是否相等。

• 当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1；举个例子，比如对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + 1 = 1。
• 当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比如对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值，即 1。

这里再解释一下不等于的情况，假设还是 ace和bc，e不等于c，则保底的情况就是倒退到没遍历到c的时候的最大长度，也就是ace和b。还有另一个情况就是加入c但是倒退ace，变成ac和bc。这两种取其中长的作为答案。
这块画成二维数组更好理解。

完整代码

定义成i-1:
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j] 表示 两字符串均到i-1时的最长公共子串。

        dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]
        for i in range(1,len(text1)+1):
            for j in range(1,len(text2)+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])

        print(dp[-1][-1])
        return dp[-1][-1]
定义成i：
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        nums1 = text1
        nums2 = text2

        # dp[i][j] 表示 两字符串均到i时的最长公共子串。
        dp = [[0 for _ in range(len(nums1))] for _ in range(len(nums2))]
        res = 0
        # 初始化第一行。
        for i in range(len(nums1)):
            if nums2[0] == nums1[i]:
                dp[0][i] = 1
            else:
                dp[0][i] =dp[0][i-1]

        # 初始化第一列
        for i in range(len(nums2)):
            if nums1[0] == nums2[i]:
                dp[i][0] = 1
            else:
                dp[i][0] = dp[i-1][0]

        for i in range(1,len(nums2)):
            for j in range(1,len(nums1)):
                if nums1[j] == nums2[i]:
                    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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

1035. 不相交的线：

这道题看图：

题目中这连线相同的值，并且说这个连线不能相交，这不是在找数组A和数组B的公共子序列嘛。

只不过这里有个不能相交的规定，那就是子序列在两个数组里的相对位置是一样的嘛。
比如 142 和124，子序列为14，在A中 顺序是1 然后4，在数组B中也是先1后4。
其实转化问题之后，这道题就是在求数组A和数组B的公共子序列。

和上一个 1143题一模一样，连代码都不用改，直接怼两道题。

当然，变量名得改一下。

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j] 表示A数组下标到i-1 B数组下标到i-1 时的公共最长子序列

        dp = [[0 for _ in range(len(nums2) + 1)] for _ in range(len(nums1) + 1)]
        for i in range(1, len(nums1) + 1):
            for j in range(1,len(nums2) + 1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        print(dp[-1][-1])
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13