代码随想录第38天：动态规划11（编辑距离）

一、编辑距离（Leetcode 72）

1.dp数组定义：

dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。

2.状态转移：

如果 word1[i-1] == word2[j-1]：

dp[i][j] = dp[i-1][j-1]  # 无需操作

否则：

dp[i][j] = 1 + min(dp[i-1][j],    # 删除 word1[i-1]dp[i][j-1],    # 插入 word2[j-1]dp[i-1][j-1]   # 替换 word1[i-1] 为 word2[j-1]
)

3.dp数组初始化：

# 初始化第一行和第一列for i in range(m + 1):dp[i][0] = i  # 只能删除 i 次for j in range(n + 1):dp[0][j] = j  # 只能插入 j 次

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)# dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符的最小操作数dp = [[0] * (n + 1) for _ in range(m + 1)]# 初始化第一行和第一列for i in range(m + 1):dp[i][0] = i  # 只能删除 i 次for j in range(n + 1):dp[0][j] = j  # 只能插入 j 次# 状态转移for i in range(1, m + 1):for j in range(1, n + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1]  # 字符相同，无需操作else:dp[i][j] = 1 + min(dp[i - 1][j],    # 删除dp[i][j - 1],    # 插入dp[i - 1][j - 1] # 替换)return dp[m][n]

二、回文子串（Leetcode 647）

• 回文字符串是正着读和反着读都相同的字符串。

• 子串是连续的字符序列。

1.dp数组定义：

dp[i][j] 表示字符串 s[i:j+1] 是否为回文子串

2.状态转移：

情况一：s[i] != s[j]

• 直接不是回文串，无需进一步判断，dp[i][j] = False

情况二：s[i] == s[j]

• 如果两端字符相等，还有两种情况：

子情况 1：j - i <= 2（子串长度为 1 或 2 或 3）

• 说明内部要么没有字符（如 a）、一个字符（如 aa）、两个字符（如 aba），这种情况下：

  • s[i+1..j-1] 最多是一个字符（或为空），肯定是回文 ⇒ 所以 dp[i][j] = True

子情况 2：j - i > 2（子串长度 ≥ 4）

• 比如 s = "abcba"，i=0, j=4

• 我们还需要看中间那部分 s[i+1..j-1] = "bcb" 是否为回文

  • 如果 dp[i+1][j-1] = True，再加上 s[i] == s[j]，就说明整个 s[i..j] 是回文

3.dp数组初始化：

dp = [[False] * n for _ in range(n)]

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)# 初始化 DP 表，dp[i][j] 表示 s[i..j] 是否是回文串dp = [[False] * n for _ in range(n)]count = 0  # 统计回文子串数量# 枚举子串的右端点 jfor j in range(n):# 枚举子串的左端点 i，且 i <= jfor i in range(0, j + 1):# 满足回文条件：# 1. 两端字符相等# 2. 内部子串是回文 或 子串长度 <= 2（即中间无需判断）if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):dp[i][j] = True  # s[i..j] 是回文count += 1       # 统计数量return count

中心扩展法（子序列连续，时间复杂度 O(n²)，空间 O(1)）

核心思想：

• 每个字符可以作为奇数长度回文的中心。

• 每两个字符之间的缝隙可以作为偶数长度回文的中心。

• 一共 2n - 1 个中心点，从这些点出发向左右扩展寻找所有回文子串。

• 奇数长度回文：left 和 right 初始指向同一个字符。

• 偶数长度回文：left 和 right 初始指向相邻的两个字符。

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)count = 0# 一共有 2n - 1 个中心点（n 个字符中心 + n-1 个字符之间的缝隙）for center in range(2 * n - 1):# 计算当前中心点对应的左右起点left = center // 2right = left + (center % 2)# 从中心向两边扩展，判断是否是回文串while left >= 0 and right < n and s[left] == s[right]:count += 1  # 找到一个回文子串left -= 1   # 向左扩展right += 1  # 向右扩展return count

三、最长回文子序列（Leetcode 516）

1.dp数组定义：

定义 dp[i][j] 表示字符串 s 的子串 s[i:j+1]（从索引 i 到 j）中最长回文子序列的长度。

目标是计算 dp[0][n-1]，即整个字符串的最长回文子序列长度。

2.状态转移：

• 情况 1：如果 s[i] == s[j]（两端字符相同）：

  • 这两个字符可以作为回文子序列的一部分。

  • 因此，dp[i][j] = dp[i+1][j-1] + 2（加上两端的两个字符）。

• 情况 2：如果 s[i] != s[j]（两端字符不同）：

  • 无法同时使用两端字符，选择去掉一端后较长的回文子序列。

  • 因此，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

3.dp数组初始化：

• 当 i == j（单个字符），dp[i][i] = 1（单个字符是长度为 1 的回文子序列）。

• 当 i > j，dp[i][j] = 0（空序列）。

class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)# 初始化 DP 表dp = [[0] * n for _ in range(n)]# 每个字符本身是一个长度为 1 的回文子序列for i in range(n):dp[i][i] = 1# 按照子串长度从 2 到 n 填充 DP 表for length in range(2, n + 1):# 枚举子串的起始位置for i in range(n - length + 1):j = i + length - 1  # 子串的结束位置# 两端字符相同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 dp[0][n - 1]