线性DP

2026-02-13

1. 最长公共子序列

(1143）给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
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

```python
class Solution:
   def longestCommonSubsequence(self, text1: str, text2: str) -> int:
       @cache
       def dfs(i,j):
           if i < 0 or j < 0:
               return 0
           if text1[i] == text2[j]:
               return dfs(i-1, j-1) + 1
           return max(dfs(i-1,j), dfs(i,j-1))
       s = len(text1)
       t = len(text2)

       def dp1():
           dp_map = [[0] * ( t+1 ) for _ in range(s + 1)]
           for i in range(s):
               for j in range(t):
                   dp_map[i+1][j+1] = dp_map[i][j]+1 if text1[i] == text2[j] else max(dp_map[i][j+1], dp_map[i+1][j])
           return dp_map[s][t]
       
       def dp2():
           dp_map = [0] * ( t+  1)
           for i in range(s):
               pre = dp_map[0]
               for j in range(t):
                   tmp  = dp_map[j +1 ]
                   dp_map[j+1] = pre + 1 if text1[i] == text2[j] else max (dp_map[j+1], dp_map[j])
                   pre = tmp
           return dp_map[t]
       return dp2()

2. 编辑距离

(72）给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
1
2
3

```python