别再死记硬背了！动态规划解回文问题的填表顺序与状态定义保姆级图解

动态规划解回文问题从填表顺序到状态定义的思维重塑第一次接触回文串的动态规划解法时我盯着那个双重循环的填表顺序发呆了半小时——为什么i要从n-1开始倒着遍历为什么j又要从i开始正着遍历更让我困惑的是dp[i][j]有时候表示子串有时候又表示子序列它们到底有什么区别直到我在白板上画了十几张填表过程图才突然明白动态规划解回文问题的精髓全藏在表格的填充顺序和状态定义里。1. 回文问题的两种面孔子串与子序列的本质区别很多人在学习时会混淆回文子串和回文子序列其实它们的区别就像DNA双链和单链回文子串必须连续就像双链DNA的严格配对示例aabaa中aba是子串状态定义dp[i][j]表示s[i...j]是否是回文回文子序列可以不连续像单链DNA的自由组合示例aabaa中aaa是子序列状态定义dp[i][j]表示s[i...j]中最长回文子序列长度# 子串判断核心代码 def is_palindrome_substring(s): n len(s) dp [[False]*n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: dp[i][j] True if (j-i1) else dp[i1][j-1] # 子序列计算核心代码 def longest_palindrome_subseq(s): n len(s) dp [[0]*n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: dp[i][j] 1 if ij else (2 if i1j else dp[i1][j-1]2) else: dp[i][j] max(dp[i1][j], dp[i][j-1])关键洞察子串关注是否子序列关注多长。这个根本差异导致了状态转移方程的不同。2. 填表顺序的奥秘为什么必须从下往上、从左往右动态规划的填表顺序不是随意决定的。让我们用二维矩阵可视化这个过程假设字符串sabca我们创建一个4x4的dp表a b c a a □ □ □ □ b □ □ □ c □ □ a □2.1 填表的依赖关系观察状态转移方程子串dp[i][j] dp[i1][j-1]子序列dp[i][j] dp[i1][j-1] 2或max(dp[i1][j], dp[i][j-1])发现了吗计算dp[i][j]需要知道左下角的dp[i1][j-1]正下方的dp[i1][j]左边的dp[i][j-1]2.2 正确的填表顺序填表顺序理由图示i从n-1到0确保dp[i1][...]已计算↓j从i到n-1确保dp[...][j-1]已计算→如果顺序错误会怎样先i从小到大计算dp[i]时dp[i1]还没算完先j从大到小计算dp[j]时dp[j-1]还没算完# 错误的填表示例会导致错误结果 for i in range(n): # 应该从n-1到0 for j in range(n-1, i-1, -1): # 应该从i到n-1 # 计算dp[i][j]...3. 状态定义的实战应用五类经典回文问题3.1 回文子串计数LeetCode 647状态定义dp[i][j]表示s[i...j]是否是回文填表技巧单个字符必是回文ij两个相同字符是回文ji1且s[i]s[j]三个以上字符取决于两端和内部s[i]s[j]且dp[i1][j-1]def countSubstrings(s): n len(s) dp [[False]*n for _ in range(n)] count 0 for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: if j - i 1: dp[i][j] True count 1 elif dp[i1][j-1]: dp[i][j] True count 1 return count3.2 最长回文子串LeetCode 5状态定义扩展在计数基础上记录最大长度和起始位置def longestPalindrome(s): n len(s) dp [[False]*n for _ in range(n)] max_len, start 1, 0 for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: if j - i 1: dp[i][j] True else: dp[i][j] dp[i1][j-1] if dp[i][j] and j-i1 max_len: max_len j - i 1 start i return s[start:startmax_len]3.3 回文子序列问题LeetCode 516状态转移的三种情况两端字符相等dp[i1][j-1] 2不等取左边或上边的最大值边界条件单个字符长度为1两个相同字符长度为2def longestPalindromeSubseq(s): 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]4. 高级应用回文分割与构造问题4.1 分割回文串IVLeetCode 1745解题思路先构建标准的回文子串dp表然后寻找两个分割点将字符串分成三个回文部分def checkPartitioning(s): n len(s) dp [[False]*n for _ in range(n)] for i in range(n-1, -1, -1): for j in range(i, n): if s[i] s[j]: dp[i][j] True if j-i1 else dp[i1][j-1] for i in range(1, n-1): for j in range(i, n-1): if dp[0][i-1] and dp[i][j] and dp[j1][n-1]: return True return False4.2 最少插入次数构造回文LeetCode 1312状态定义转变dp[i][j]表示使s[i...j]成为回文的最少插入次数转移方程s[i]s[j]不需要额外插入dp[i][j] dp[i1][j-1]s[i]!s[j]在左边或右边插入一个字符取较小值1def minInsertions(s): n len(s) dp [[0]*n for _ in range(n)] 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] else: dp[i][j] min(dp[i1][j], dp[i][j-1]) 1 return dp[0][n-1]5. 调试技巧与常见陷阱在实现回文问题的动态规划解法时有几个容易踩坑的地方边界条件处理子串ij时为Truei1j时检查s[i]s[j]子序列ij时长度为1i1j时长度为2如果相等填表范围控制j的起始点必须是i因为ji的区域无意义子序列问题中j从i1开始可以避免单独处理ij的情况空间优化可能性由于i只依赖i1可以压缩成一维数组但会损失填表过程的可视化调试能力# 空间优化版本以最长回文子序列为例 def longestPalindromeSubseq_optimized(s): n len(s) dp [1]*n for i in range(n-1, -1, -1): prev 0 # 记录dp[i1][j-1] for j in range(i1, n): temp dp[j] if s[i] s[j]: dp[j] prev 2 else: dp[j] max(dp[j], dp[j-1]) prev temp return dp[n-1]调试建议当你的代码出现问题时尝试在纸上画出dp表的填充过程特别是检查每个dp[i][j]是否正确依赖了dp[i1][j-1]、dp[i1][j]和dp[i][j-1]。