应用题-动态规划-不相交的线( 本质:最长公共子序列 )
- 版权声明：本站原创文章，于2026-06-02，由 管理员 发表。
- 转载请注明： 应用题-动态规划-不相交的线( 本质:最长公共子序列 ) | CodeGarden
```python
class Solution:
# 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
# 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
# - nums1[i] == nums2[j]
# - 且绘制的直线不与任何其他连线（非水平线）相交。
# 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
# 以这种方法绘制线条，并返回可以绘制的最大连线数。
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
# 应用题:本质 -> nums1和nums2中元素可删除 求最长公共子序列
n1, n2 = len( nums1 ), len( nums2 )
if n1 == 0 or n2 == 0: return 0
dp = [ [ 0 for _ in range( n2 + 1 ) ] for _ in range( n1 + 1 ) ]
ans = 0
for i in range( 1, n1 + 1 ):
for j in range( 1, n2 + 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 - 1 ], dp[ i ][ j - 1 ], dp[ i - 1 ][ j ] )
if dp[ i ][ j ] > ans: ans = dp[ i ][ j ]
return ans
```