583. 两个字符串的删除操作
方法一：动态规划最长公共子序列：Longest Common Subsequence 简称 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, 列 n
for i in range(m):
for j in range(n):
if text1[i] == text2[j]:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
return dp[m][n]
二维数组到一维数组的优化
对动态规划进行了优化，因为只涉及到两行，分别定义两个变量记录。
| j | j + 1 | ||
|---|---|---|---|
| a | …… | a[j] | a[j+1] |
| b | …… | 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 m
if 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] + 1
else: b[j+1] = max(b[j],a[j+1])
a, b = b, a
return 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 m
if text2 in text1: return n
dp = [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 + 1
else:
dp[j+1] = max(dp[j],dp[j+1])
upLeft = tmp # 下一次作为 dp[i][j] 用
return dp[n]
516. 最长回文子序列
方法一：递归 + 双指针
取 s 的首尾两字母 x 和 y，如果 x == y，除去 x、y 的最长回文子序列的长度 + 2，如果 x != y 除去 x 或 y 的最大的回文子序列长度中的最大值。
如： “bbbab”，“bba” 最大的回文子序列的长度 + 2，“ba” 和 “bb” 最大值是 2。
class Solution:
@lru_cache(None)
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
if n < 2: return n
l, r = 0, len(s)-1
while l < r:
if s[l] == s[r]:
return self.longestPalindromeSubseq(s[l+1:r]) + 2
else:
return max(self.longestPalindromeSubseq(s[l+1:r+1]), self.longestPalindromeSubseq(s[l:r]))
方法二：递归
对 s 中的每一个字母都要遍历，取最大值，超时。
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
if n < 2: return n
res = 0
for i, c in enumerate(s):
r = str.rindex(s, c)
if r > i:
res = max(res, self.longestPalindromeSubseq(s[i+1:r]) + 2)
else:
res = max(res, 1)
return res
方法三：递归 + 二分
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
if n < 2: return n
cIndex = defaultdict(list)
for i, c in enumerate(s): cIndex[ord(c) - ord('a')].append(i)
@lru_cache(None)
def dfs(l, r):
if l >= r: return 1 if l == r else 0
ans = 0
for i in range(26):
left = bisect.bisect_left(cIndex[i], l)
if left == len(cIndex[i]): continue
right = bisect.bisect_left(cIndex[i], r)
print(right,)
if right == len(cIndex[i]) or cIndex[i][right] > r:
right -= 1
ans = max(ans, dfs(cIndex[i][left]+1, cIndex[i][right]-1) + 2) if right > left else max(ans, 1)
return ans
return dfs(0, n-1)
方法四：动态规划
dp[i][j] 表示字符串 s 的下标区间 [i, j] 内的最长回文子序列的长度。
dp = [[0] * n for _ in range(n)] # n = len(s) dp[i][i] = 1 # 表示单个字符的回文长度为1
d p [ i ] [ j ] = { d p [ i + 1 ] [ j − 1 ] + 2 s[i] == s[j] m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j − 1 ] ) s[i] != s[j] dp[i][j]= begin{cases} dp[i+1][j−1]+2& text{s[i] == s[j]}\ max(dp[i+1][j], dp[i][j−1])& text{s[i] != s[j]} end{cases} dp[i][j]={dp[i+1][j−1]+2max(dp[i+1][j],dp[i][j−1])s[i] == s[j]s[i] != s[j]
遍历方向：从下往上进行遍历
返回 dp[0][−1]
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
# dp = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
dp = [[0] * n for _ in range(n)]
for i in range(n-1,-1,-1):
dp[i][i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return n - dp[0][-1]
1312. 让字符串成为回文串的最少插入次数
方法一：动态规划
本题属于 516. 最长回文子序列 的子题，只需要用字符串长度减去最长回文子序列的长度就是最少插入次数。
注意：需要从后往前遍历，因为每一个 d p [ i ] [ j ] dp[i][j] dp[i][j] 取决于它前面的最大回文子序列长度。
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
# dp = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
dp = [[0] * n for _ in range(n)]
for i in range(n-1,-1,-1):
dp[i][i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return n - dp[0][-1]
当在字符串 s 中找到最长回文子序列后，对于在 s 中但不在子序列中的那些字符，如果其在回文中心的左侧，就在右侧对应的位置添加一个相同的字符；如果其在回文中心的右侧，就在左侧对应的位置添加一个相同的字符。
那么如何求出 s 的最长回文子序列 sPA 呢？sPA 就等同于 s 和 s[::-1] 的最长公共子序列。
参考：1143. 最长公共子序列
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
# t = s[::-1]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(n):
# if s[i] == t[j]:
if s[i] == s[-j-1]:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
return n - dp[-1][-1]
方法二：区间动态规划
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示对于字符串 s 的子串 s [ i : j + 1 ] s[i:j+1] s[i:j+1]，最少添加的字符数量，使得 s [ i : j + 1 ] s[i:j+1] s[i:j+1] 变为回文串。
求 d p [ i ] [ i + k ] dp[i][i+k] dp[i][i+k]，也就是 s [ i : i + k + 1 ] s[i:i+k+1] s[i:i+k+1] 变成回文字符串的最少插入次数。
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for k in range(1,n):
for i in range(n-k):
if s[i] == s[i+k]:
dp[i][i+k] = dp[i+1][i+k-1]
else:
dp[i][i+k] = min(dp[i+1][i+k] + 1, dp[i][i+k-1] + 1)
return dp[0][-1]
