动态规划实战：字符串操作与编辑距离解析

1. 动态规划专题精讲字符串操作与编辑距离实战作为一名刷过300动态规划题的算法工程师我深知字符串相关的DP问题是面试中最常出现的拦路虎。这次代码随想录训练营的55-57天内容恰好覆盖了字符串处理的六大经典题型。我将结合自己在大厂面试中出题和解题的双重经验带大家深度剖析这些题目背后的统一解题框架。2. 核心题目解析与DP定义2.1 判断子序列392题这道题看似简单却暗藏玄机。给定字符串s和t判断s是否为t的子序列。双指针解法虽然直观但DP解法才是理解后续难题的基础。def isSubsequence(s: str, t: str) - bool: dp [[0]*(len(t)1) for _ in range(len(s)1)] for i in range(1, len(s)1): for j in range(1, len(t)1): if s[i-1] t[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] dp[i][j-1] # 只能删除t的字符 return dp[-1][-1] len(s)关键点在于dp[i][j]表示s[0:i]和t[0:j]的最长公共子序列长度。当字符不匹配时只能选择删除t的字符j前移这与后续115题形成鲜明对比。2.2 不同的子序列115题这道hard题让很多同学头疼其实只要理解状态转移的物理意义就能迎刃而解。求s中通过删除字符得到t的不同方式数目需要特别注意初始化条件和递推关系。def numDistinct(s: str, t: str) - int: dp [[0]*(len(s)1) for _ in range(len(t)1)] for j in range(len(s)1): dp[0][j] 1 # 空串是任何字符串的子序列 for i in range(1, len(t)1): for j in range(1, len(s)1): if t[i-1] s[j-1]: dp[i][j] dp[i-1][j-1] dp[i][j-1] else: dp[i][j] dp[i][j-1] return dp[-1][-1]关键技巧当s[j-1]匹配t[i-1]时可以选择匹配或者不匹配相当于删除s的字符这是与392题的本质区别。3. 编辑距离系列问题3.1 两个字符串的删除操作583题这道题可以看作编辑距离的简化版只允许删除操作。我发现很多同学会陷入一个误区——直接求最长公共子序列然后用总长度减去。其实更直观的DP定义是def minDistance(word1: str, word2: str) - int: dp [[0]*(len(word2)1) for _ in range(len(word1)1)] for i in range(len(word1)1): dp[i][0] i for j in range(len(word2)1): dp[0][j] j for i in range(1, len(word1)1): for j in range(1, len(word2)1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1]) 1 return dp[-1][-1]3.2 编辑距离72题这是DP领域的经典问题也是谷歌面试的高频题。完整的编辑距离需要考虑插入、删除、替换三种操作。我在面试候选人时最看重的是能否说清楚状态转移方程的物理意义。def minDistance(word1: str, word2: str) - int: dp [[0]*(len(word2)1) for _ in range(len(word1)1)] for i in range(len(word1)1): dp[i][0] i for j in range(len(word2)1): dp[0][j] j for i in range(1, len(word1)1): for j in range(1, len(word2)1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min( dp[i-1][j], # 删除word1[i-1] dp[i][j-1], # 插入word2[j-1] dp[i-1][j-1] # 替换 ) 1 return dp[-1][-1]实战经验在面试白板编程时建议先写出状态转移方程再写代码这样即使代码有小错误面试官也能理解你的思路。4. 回文串专题4.1 回文子串647题这道题要求统计字符串中回文子串的数量。常规中心扩展法虽然简单但DP解法更能锻炼思维。我推荐使用二维DP记录子串[i,j]是否为回文。def countSubstrings(s: str) - int: n len(s) dp [[False]*n for _ in range(n)] res 0 for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: if j - i 1: res 1 dp[i][j] True elif dp[i1][j-1]: res 1 dp[i][j] True return res4.2 最长回文子序列516题与子串不同子序列不要求连续。这道题的DP定义非常巧妙dp[i][j]表示s[i..j]的最长回文子序列长度。def longestPalindromeSubseq(s: str) - int: n len(s) dp [[0]*n for _ in range(n)] for i in range(n): dp[i][i] 1 for i in range(n-1, -1, -1): for j in range(i1, n): if s[i] s[j]: dp[i][j] dp[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1]) return dp[0][n-1]5. 动态规划解题方法论通过这六道题的训练我总结出字符串DP问题的通用解题框架明确DP数组含义90%的困难来自于定义不清确定初始条件特别是空字符串的处理分析状态转移字符匹配/不匹配时的不同处理考虑遍历顺序i/j的递增或递减方向影响结果验证边界条件单字符、空串等特殊情况常见错误排查表错误现象可能原因解决方案数组越界初始化不全检查dp数组行列数是否1结果偏小状态转移漏情况重新分析字符匹配时的选择结果偏大重复计算检查递推公式是否包含多余操作超时未优化空间考虑状态压缩如滚动数组在面试场景中建议按照以下步骤应对DP问题先用具体例子画出DP表格口头解释状态转移逻辑写出基础状态转移方程讨论边界条件和初始化最后编码实现6. 进阶训练建议掌握这些基础题型后可以尝试以下变种题目提升能力最短回文串添加214题回文分割II132题正则表达式匹配10题通配符匹配44题我个人的训练心得是每天坚持做2道DP题一个月后会有质的飞跃。建议准备一个错题本记录每道题的DP定义和状态转移方程定期复习。对于字符串DP问题要特别注意画图辅助理解推荐使用二维表格可视化递推过程。