模版题-动态规划-最长公共子序列( 对比:最长重复子数组 )
- 版权声明：本站原创文章，于2026-06-02，由 管理员 发表。
- 转载请注明： 模版题-动态规划-最长公共子序列( 对比:最长重复子数组 ) | CodeGarden
**遇到不同字符时，如何处理!**
```python
class Solution:
# 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
# 如果不存在 公共子序列 ，返回 0 。
# 一个字符串的子序列是指这样一个新的字符串：
# 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
# 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
# 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n1, n2 = len( text1 ), len( text2 )
if n1 == 0 or n2 == 0: return 0
# dp[ i ][ j ]表示:
# 以 text1[ i - 1 ]结尾的字符串A
# 以 text2[ j - 1 ]结尾的字符串B
# A和B的最长公共子序列为dp[ i ][ j ]
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 text1[ i - 1 ] == text2[ j - 1 ]:
# 找到一个公共字符
dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + 1
else:
# 删除不相等的字符
dp[ i ][ j ] = max( dp[ i - 1 ][ j - 1 ], dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] )
if dp[ i ][ j ] > ans: ans = dp[ i ][ j ]
return ans
```