1. 动态规划专题字符串操作精要解析最近在算法训练中字符串相关的动态规划问题总是让人又爱又恨。特别是当遇到子序列、编辑距离这类经典题目时很多同学都会陷入状态转移的迷雾中。今天我就结合代码随想录训练营的几道经典题目分享一下我的解题心得和实战经验。字符串DP问题在面试和竞赛中出现的频率极高从简单的判断子序列到复杂的编辑距离计算考察的都是我们对动态规划思想的掌握程度。这类问题通常需要构建二维DP数组通过分析字符匹配情况来推导状态转移方程。下面我们就从最基础的392题开始逐步深入看看如何用动态规划解决这些看似复杂的问题。2. 判断子序列问题解析2.1 392.判断子序列问题分析判断子序列是字符串DP中最基础的入门题。题目给定字符串s和t要求判断s是否是t的子序列。这里的子序列指的是在不改变字符顺序的情况下通过删除某些字符可以得到的序列。这道题有两种经典解法双指针法和动态规划法。双指针法思路简单直接时间复杂度O(n)空间复杂度O(1)是更优的选择。但为了后续题目铺垫我们重点讨论DP解法。DP解法的核心是将其转化为最长公共子序列(LCS)问题。定义dp[i][j]表示s的前i个字符和t的前j个字符的最长公共子序列长度。状态转移方程为if s[i-1] t[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] dp[i][j-1]最终判断dp[len(s)][len(t)]是否等于len(s)即可。注意在实际编码时建议将dp数组行列都多开一位这样可以避免处理边界条件减少出错概率。2.2 代码实现与优化虽然DP解法不是最优解但理解它对于后续题目非常重要。下面给出Python实现def isSubsequence(s: str, t: str) - bool: m, n len(s), len(t) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): if s[i-1] t[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] dp[i][j-1] return dp[m][n] m对于空间优化可以观察到dp[i][j]只依赖于上一行和当前行的前一个状态因此可以将空间复杂度优化到O(n)def isSubsequence(s: str, t: str) - bool: m, n len(s), len(t) dp [0]*(n1) for i in range(1, m1): prev 0 for j in range(1, n1): temp dp[j] if s[i-1] t[j-1]: dp[j] prev 1 else: dp[j] dp[j-1] prev temp return dp[n] m3. 不同的子序列问题3.1 115.不同的子序列问题分析这道题难度明显提升要求计算s中可以通过删除字符得到t的不同子序列的个数。例如srabbbittrabbit返回3。定义dp[i][j]表示s的前i个字符中t的前j个字符出现的次数。状态转移需要考虑两种情况当s[i-1]t[j-1]时可以选择匹配或者不匹配当不相等时只能选择不匹配状态转移方程if s[i-1] t[j-1]: dp[i][j] dp[i-1][j-1] dp[i-1][j] else: dp[i][j] dp[i-1][j]初始化时dp[i][0]1因为空串是任何字符串的子序列。3.2 边界条件处理这类计数问题的边界条件特别容易出错。需要注意当s为空时除了t也为空的情况其他都返回0当t为空时返回1当s长度小于t长度时直接返回0Python实现def numDistinct(s: str, t: str) - int: m, n len(s), len(t) if m n: return 0 dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] 1 for i in range(1, m1): for j in range(1, n1): if s[i-1] t[j-1]: dp[i][j] dp[i-1][j-1] dp[i-1][j] else: dp[i][j] dp[i-1][j] return dp[m][n]实战技巧这类问题如果使用递归记忆化会更容易理解但在面试时建议优先展示DP解法因为它的时间复杂度更优且更能体现算法功底。4. 字符串删除操作问题4.1 583.两个字符串的删除操作这道题要求计算使word1和word2相同所需的最小删除步数。实际上就是求两个字符串长度之和减去两倍的LCS长度。定义dp[i][j]表示word1前i个字符和word2前j个字符的LCS长度。状态转移方程if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])最终结果为len(word1)len(word2)-2*dp[m][n]。4.2 空间优化技巧由于DP只依赖上一行和当前行可以进行空间优化def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [0]*(n1) for i in range(1, m1): prev 0 for j in range(1, n1): temp dp[j] if word1[i-1] word2[j-1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j-1]) prev temp return m n - 2 * dp[n]5. 编辑距离问题5.1 72.编辑距离深度解析编辑距离是字符串DP中最经典的问题之一要求计算将word1转换成word2所需的最少操作次数插入、删除、替换。定义dp[i][j]表示word1前i个字符转换成word2前j个字符的最小操作次数。状态转移需要考虑三种操作插入dp[i][j] dp[i][j-1] 1删除dp[i][j] dp[i-1][j] 1替换如果word1[i-1]word2[j-1]则不需要操作否则dp[i][j] dp[i-1][j-1] 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], dp[i-1][j-1]) 15.2 代码实现与优化Python实现def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): 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], dp[i-1][j-1]) 1 return dp[m][n]空间优化版本def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) dp [j for j in range(n1)] for i in range(1, m1): prev dp[0] dp[0] i for j in range(1, n1): temp dp[j] if word1[i-1] word2[j-1]: dp[j] prev else: dp[j] min(dp[j], dp[j-1], prev) 1 prev temp return dp[n]6. 回文子串问题6.1 647.回文子串问题分析这道题要求计算字符串中回文子串的数量。与前面的问题不同这里需要判断所有可能的子串是否为回文。有两种常用解法中心扩展法和动态规划法。DP解法定义dp[i][j]表示s[i..j]是否为回文。状态转移方程if s[i] s[j]: if j - i 1: dp[i][j] True else: dp[i][j] dp[i1][j-1] else: dp[i][j] False6.2 中心扩展法实现虽然DP解法直观但中心扩展法更高效def countSubstrings(s: str) - int: n len(s) res 0 for i in range(n): # 奇数长度 l, r i, i while l 0 and r n and s[l] s[r]: res 1 l - 1 r 1 # 偶数长度 l, r i, i1 while l 0 and r n and s[l] s[r]: res 1 l - 1 r 1 return res7. 最长回文子序列问题7.1 516.最长回文子序列问题解析这道题要求找出字符串中最长的回文子序列的长度。注意子序列可以不连续。定义dp[i][j]表示s[i..j]的最长回文子序列长度。状态转移方程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])7.2 代码实现与遍历顺序实现时需要注意遍历顺序i从大到小j从小到大def longestPalindromeSubseq(s: str) - int: n len(s) dp [[0]*n for _ in range(n)] for i in range(n-1, -1, -1): dp[i][i] 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]8. 动态规划问题解题框架总结通过以上六道题目的分析我们可以总结出字符串DP问题的通用解题框架定义DP数组的含义通常与子序列/子串相关确定初始条件空串、单字符等情况分析状态转移方程字符匹配/不匹配时的不同情况确定遍历顺序自顶向下或自底向上考虑空间优化滚动数组等技巧对于回文类问题还需要特别注意中心扩展法往往比DP更高效遍历顺序需要根据问题特点调整边界条件处理要格外小心在实际面试中建议先明确DP定义和状态转移方程再开始编码。可以先写基础版本再讨论优化空间的可能性。对于特别复杂的问题可以先从递归记忆化入手再转化为DP解法。
