1143. 最长公共子序列

1143. 最长公共子序列
583. 两个字符串的删除操作
方法一：动态规划
最长公共子序列：简称 LCS
状态定义： dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 的长度
初始化： dp = [[0] * (n + 1) for _ in range(m + 1)]
注意行 m, 列 n，dp[0][0] 表示 text1 = text2 = “” 。
转移方程：
d p [ i + 1 ] [ j + 1 ] = { d p [ i ] [ j ] + 1 text1[i]==text2[j] m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j + 1 ] ) text1[i]!=text2[j] dp[i+1][j+1]= \begin{cases} dp[i][j]+1 & \text{text1[i] == text2[j]}\\ max(dp[i + 1][j], dp[i][j +1]) & \text{text1[i] != text2[j]} \end{cases} dp[i+1][j+1]={dp[i][j]+1max(dp[i+1][j],dp[i][j+1])?text1[i]==text2[j]text1[i]!=text2[j]?

文章插图
为了避免判断 i - 1，j - 1 合法性，直接定义 dp 数组 (n+1) * (m+1) 。注意 dp 与 text 的索引

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)] # 行 m, 列 nfor i in range(m):for j in range(n):if text1[i] == text2[j]:dp[i+1][j+1] = dp[i][j] + 1else:dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])return dp[m][n]

二维数组到一维数组的优化
对动态规划进行了优化，因为只涉及到两行，分别定义两个变量记录。
jj + 1
【1143. 最长公共子序列】……
a[j]
a[j+1]
……

文章插图
b[j]
b[j+1]

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2)if text1 in text2: return mif text2 in text1: return n a, b = [0] * (n + 1),[0] * (n + 1)for i in range(m):for j in range(n):if text1[i] == text2[j]: b[j+1] = a[j] + 1else: b[j+1] = max(b[j],a[j+1])a, b = b, areturn a[n]

二维数组到一维数组的优化
对动态规划进行了优化，因为只涉及到两行，用到第一行与第二行前面数据，所以可以优化到一维数组。
比如计算 dp[2][2] 的时候, 可能用到 dp[1][1], dp[1][2], 和dp[2][1] 。左侧数据在同一行，上方数据还未被覆盖，注意左上方的数据，因为在计算前一列的时候可能会被覆盖，需要保存。

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2)if text1 in text2: return mif text2 in text1: return ndp = [0] * (n + 1)for i in range(m):upLeft = dp[0] # 每一行的开始都是 0 for j in range(n):tmp = dp[j + 1] # 缓存 dp[j + 1], 后面会被覆盖 。if text1[i] == text2[j]: dp[j+1] = upLeft + 1else: dp[j+1] = max(dp[j],dp[j+1])upLeft = tmp# 下一次作为 dp[i][j] 用return dp[n]