线性DP

2026-02-13

1. 最长公共子序列

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

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

 输入：text1 = "abcde", text2 = "ace"   
 输出：3    
 解释：最长公共子序列是 "ace" ，它的长度为 3 。

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’) `

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        @cache
        def dfs(i,j):
            if i<0 or j<0:
                return abs(i-j)
            if word1[i] ==word2[j]:
                return dfs(i-1, j-1)
            else:
                return min( dfs(i-1,j), dfs(i,j-1), dfs(i-1,j-1)) + 1
        def dp1():
            dp_map = [[0] * (t+1) for _ in range(s+1)]
            for i in range(s+1):
                for j in range(t+1):
                    if i==0 or j==0:
                        dp_map[i][j] = i+j
                    else:
                        dp_map[i][j] = dp_map[i-1][j-1] if word1[i-1]==word2[j-1] else min(dp_map[i-1][j], dp_map[i][j-1], dp_map[i-1][j-1]) + 1
            return dp_map[s][t]
        def dp2():
            dp_map  = list(range(t + 1))
            for i in range(s):
                pre = dp_map[0]
                dp_map[0] = i+1
                for j in range(t):
                    tmp = dp_map[j+1]
                    dp_map[j+1] = pre if word1[i] == word2[j] else min(dp_map[j+1], dp_map[j], pre) + 1
                    pre = tmp
            return dp_map[t]