题目描述
给了两个数组，可以把数组中相同的数组连起来，限制条件是连线不能相交
问最多能连多少根？
| f1-最长公共子序列 |
基本分析
- 为啥不能贪心？例如134和341，如果1一定要往后取，只能1，最好的结果是2
- 怎么变形？找到两个字符串的LCS，可以满足索引的限制要求
- 为啥在求LCS的时候会存在重复情况？状态定义为f[i][j]表示前i序列和前j序列的LCS值，这里可以不一定要求包含第i和第j个字符。对于而包含情况会有
| s1[i] | s2[j] | 表示 |
|---|---|---|
| 不含 | 不含 | f[i-1][j-1] |
| 包含 | 包含 | f[i-1][j-1] + 1 |
| 不含 | 包含 | 无法表示 1+3 = f[i-1][j] |
| 包含 | 不含 | 无法表示 1+3 = f[i][j-1] |
因为是求max，保证不漏就行，不需要不重，所以2、3、4可以包含所有情况
代码
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m+1):
for j in range(1, n+1):
f[i][j] = max(f[i-1][j], f[i][j-1])
if nums1[i-1] == nums2[j-1]:
f[i][j] = max(f[i][j], f[i-1][j-1] + 1)
return f[m][n]
总结
- 能看出来不是贪心
- 能看出来是LCS的变形题
- 能深刻理解状态定义的含义，理解为啥进行了重复计算，但是又可以重复计算
- 在定义状态的时候因为有-1的情况，多定义了一位，从1开始遍历