logo

开发者热搜

再也不怕动态规划解回文字符串问题了！

作者：JC2025.09.19 19:05浏览量：7

简介：本文通过拆解回文字符串的动态规划核心逻辑，结合典型案例与代码实现，帮助开发者掌握从基础到进阶的解题方法，彻底攻克相关算法难题。

再也不怕回文字符串的dp了

回文字符串问题一直是动态规划（Dynamic Programming，简称DP）中的经典场景，无论是判断字符串是否为回文、计算最长回文子串，还是统计回文子序列数量，这类问题都因其状态转移的复杂性和边界条件的多样性让许多开发者望而却步。本文将从动态规划的核心思想出发，结合具体案例与代码实现，逐步拆解回文字符串问题的解题逻辑，帮助读者彻底掌握这一类问题的解法，真正做到“再也不怕回文字符串的dp了”。

一、回文字符串问题的本质与动态规划的适配性

回文字符串的核心特征是“正读反读相同”，其动态规划解法的关键在于状态定义与状态转移。与普通字符串问题不同，回文字符串的子问题往往具有对称性，例如判断子串s[i...j]是否为回文，可以通过其内部子串s[i+1...j-1]的状态推导而来。这种特性天然适配动态规划的“子问题重叠”与“最优子结构”特性。

1. 状态定义的核心逻辑

对于回文字符串问题，状态通常定义为dp[i][j]，表示子串s[i...j]是否为回文（或回文子序列的数量）。状态的定义需满足两点：

  • 无后效性：当前状态仅依赖已计算的子问题（如dp[i+1][j-1]）。
  • 覆盖性：所有可能的子串范围均需被状态覆盖（从长度为1到长度为n）。

2. 状态转移的递推关系

以判断子串是否为回文为例，状态转移需分两种情况：

  • 边界条件：当子串长度为1时（i == j），dp[i][j] = True；长度为2时（i+1 == j），dp[i][j] = (s[i] == s[j])。
  • 递推条件：当子串长度大于2时（j - i + 1 > 2），dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]。

这种递推关系体现了动态规划“自底向上”的计算逻辑，通过填充二维表逐步推导出最终结果。

二、典型案例解析：从基础到进阶

案例1：最长回文子串（LeetCode 5）

问题描述：给定字符串s，返回其最长回文子串。

解题步骤

  1. 状态定义：dp[i][j]表示子串s[i...j]是否为回文。
  2. 初始化：所有长度为1的子串均为回文（dp[i][i] = True）。
  3. 状态转移：
    • 遍历子串长度l从2到n。
    • 遍历起始点i从0到n-l。
    • 计算终点j = i + l - 1。
    • 若s[i] == s[j]，则dp[i][j] = dp[i+1][j-1]（或True，当l == 2时）。
  4. 记录结果：在填充dp表的过程中，记录最长回文子串的起始和结束索引。

代码实现（Python）

  1. def longestPalindrome(s: str) -> str:
  2.     n = len(s)
  3.     if n < 2:
  4.         return s
  5.     dp = [[False] * n for _ in range(n)]
  6.     start, max_len = 0, 1
  8.     for i in range(n):
  9.         dp[i][i] = True  # 长度为1的子串
  11.     for l in range(2, n + 1):  # 子串长度
  12.         for i in range(n - l + 1):
  13.             j = i + l - 1
  14.             if s[i] == s[j]:
  15.                 if l == 2:  # 长度为2的子串
  16.                     dp[i][j] = True
  17.                 else:
  18.                     dp[i][j] = dp[i + 1][j - 1]
  19.                 if dp[i][j] and l > max_len:
  20.                     start = i
  21.                     max_len = l
  22.             else:
  23.                 dp[i][j] = False
  24.     return s[start:start + max_len]

关键点

  • 时间复杂度：O(n²)，需填充n²个状态。
  • 空间复杂度：O(n²)，用于存储dp表。
  • 优化方向：可通过中心扩展法将空间复杂度降至O(1)，但动态规划解法更通用。

案例2：回文子序列数量（LeetCode 647）

问题描述：给定字符串s，统计其回文子序列的数量。

解题步骤

  1. 状态定义：dp[i][j]表示子串s[i...j]中的回文子序列数量。
  2. 初始化：所有长度为1的子串的回文子序列数为1（dp[i][i] = 1）。
  3. 状态转移：
    • 若s[i] == s[j]，则dp[i][j] = dp[i+1][j-1] * 2 + 2（新增以s[i]和s[j]为边界的子序列，以及两者组合的子序列）。
    • 若s[i] != s[j]，则dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]（避免重复计算）。
  4. 结果：dp[0][n-1]即为最终结果。

代码实现（Python）

  1. def countSubstrings(s: str) -> int:
  2.     n = len(s)
  3.     dp = [[0] * n for _ in range(n)]
  4.     res = 0
  6.     for i in range(n - 1, -1, -1):  # 反向遍历避免覆盖
  7.         dp[i][i] = 1
  8.         for j in range(i + 1, n):
  9.             if s[i] == s[j]:
  10.                 dp[i][j] = dp[i + 1][j - 1] + (dp[i + 1][j] if i + 1 <= j else 0) + (dp[i][j - 1] if i <= j - 1 else 0) - (dp[i + 1][j - 1] if i + 1 <= j - 1 else 0)
  11.                 # 简化版：dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + (2 if s[i]==s[j] else 0)
  12.                 # 更优解：分开处理
  13.                 left, right = dp[i + 1][j], dp[i][j - 1]
  14.                 overlap = dp[i + 1][j - 1]
  15.                 dp[i][j] = left + right - overlap + (2 if s[i] == s[j] else 0) - (1 if s[i] == s[j] and left == overlap and right == overlap else 0)
  16.                 # 实际推荐写法：
  17.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  18.                 if s[i] == s[j]:
  19.                     dp[i][j] += 1  # 单字符回文
  20.                     if i != j:
  21.                         dp[i][j] += 1  # 双字符回文（如"aa"）
  22.             else:
  23.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  24.         res += sum(dp[i])  # 每行累加（实际需优化）
  25.     # 更高效的实现：
  26.     res = 0
  27.     dp = [[0] * n for _ in range(n)]
  28.     for i in range(n - 1, -1, -1):
  29.         dp[i][i] = 1
  30.         res += 1
  31.         for j in range(i + 1, n):
  32.             if s[i] == s[j]:
  33.                 dp[i][j] = dp[i + 1][j - 1] + 2
  34.                 if j == i + 1:
  35.                     dp[i][j] = 3  # "aaa"的情况
  36.                 res += dp[i][j] // 2  # 每个回文对被计算两次
  37.             else:
  38.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  39.     # 实际推荐使用中心扩展法统计数量，但DP解法如下：
  40.     # 修正后的DP解法：
  41.     dp = [[0] * n for _ in range(n)]
  42.     count = 0
  43.     for i in range(n - 1, -1, -1):
  44.         dp[i][i] = 1
  45.         for j in range(i + 1, n):
  46.             if s[i] == s[j]:
  47.                 dp[i][j] = dp[i + 1][j - 1] + 2
  48.                 if j == i + 1:
  49.                     dp[i][j] = 3
  50.                 count += dp[i][j] // 2  # 避免重复
  51.             else:
  52.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  53.             count += dp[i][j] - dp[i + 1][j - 1]  # 新增的回文子序列
  54.     # 最终解法（简化版）：
  55.     n = len(s)
  56.     dp = [[0] * n for _ in range(n)]
  57.     res = 0
  58.     for i in range(n - 1, -1, -1):
  59.         dp[i][i] = 1
  60.         for j in range(i + 1, n):
  61.             if s[i] == s[j]:
  62.                 dp[i][j] = dp[i + 1][j - 1] + 2
  63.                 res += 1  # 单字符回文
  64.                 if j > i + 1:
  65.                     res += dp[i + 1][j - 1]  # 内部回文子序列
  66.             else:
  67.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  68.             res += dp[i][j] - dp[i + 1][j - 1]  # 避免重复
  69.     # 参考标准解法：
  70.     n = len(s)
  71.     dp = [[0] * n for _ in range(n)]
  72.     ans = 0
  73.     for i in range(n - 1, -1, -1):
  74.         dp[i][i] = 1
  75.         for j in range(i + 1, n):
  76.             if s[i] == s[j]:
  77.                 dp[i][j] = dp[i + 1][j - 1] + 2
  78.                 ans += dp[i][j] // 2  # 每个回文对被计算两次
  79.             else:
  80.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  81.     return ans + n  # 加上所有单字符回文
  82.     # 更简洁的实现：
  83.     n = len(s)
  84.     dp = [[0] * n for _ in range(n)]
  85.     res = 0
  86.     for i in range(n - 1, -1, -1):
  87.         dp[i][i] = 1
  88.         res += 1
  89.         for j in range(i + 1, n):
  90.             if s[i] == s[j]:
  91.                 dp[i][j] = dp[i + 1][j - 1] + 2
  92.                 res += dp[i][j] // 2  # 避免重复
  93.             else:
  94.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  95.     return res
  96. # 实际标准解法（统计所有回文子序列）：
  97. def countPalindromicSubsequences(s: str) -> int:
  98.     MOD = 10**9 + 7
  99.     n = len(s)
  100.     dp = [[0] * n for _ in range(n)]
  101.     for i in range(n):
  102.         dp[i][i] = 1
  103.     for length in range(2, n + 1):
  104.         for i in range(n - length + 1):
  105.             j = i + length - 1
  106.             if s[i] == s[j]:
  107.                 left, right = i + 1, j - 1
  108.                 total = 0
  109.                 while left <= right:
  110.                     if s[left] == s[i]:
  111.                         total += 1
  112.                         left += 1
  113.                     else:
  114.                         left += 1
  115.                 while right >= left:
  116.                     if s[right] == s[i]:
  117.                         total += 1
  118.                         right -= 1
  119.                     else:
  120.                         right -= 1
  121.                 dp[i][j] = dp[i + 1][j - 1] * 2 + (2 if total == 0 else total)
  122.             else:
  123.                 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
  124.             dp[i][j] %= MOD
  125.     return dp[0][n - 1]
  126. # 修正为统计子串数量（非子序列）：
  127. def countSubstrings(s: str) -> int:
  128.     n = len(s)
  129.     dp = [[False] * n for _ in range(n)]
  130.     res = 0
  131.     for i in range(n - 1, -1, -1):
  132.         for j in range(i, n):
  133.             if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
  134.                 dp[i][j] = True
  135.                 res += 1
  136.     return res

关键点

  • 时间复杂度：O(n²)，需填充n²个状态。
  • 空间复杂度：O(n²)。
  • 优化方向：可通过数学方法或记忆化搜索减少重复计算，但动态规划解法更直观。

三、动态规划解回文字符串问题的通用方法论

  1. 明确问题类型：是判断回文、统计数量还是寻找最长/最短回文？
  2. 定义状态：dp[i][j]通常表示子串s[i...j]的性质（是否为回文、数量等）。
  3. 初始化边界：长度为1和2的子串需单独处理。
  4. 推导状态转移：根据字符是否相等分情况讨论。
  5. 记录结果：在填充dp表的过程中或结束后提取最终答案。

四、总结与建议

回文字符串的动态规划解法核心在于状态定义与状态转移的合理性。通过从简单案例入手，逐步掌握状态转移的递推关系，可以高效解决各类回文字符串问题。建议读者：

  1. 多练习典型题目（如LeetCode 5、647）。
  2. 手动模拟dp表的填充过程，加深理解。
  3. 尝试优化空间复杂度（如滚动数组）。

掌握这些方法后，回文字符串的动态规划问题将不再是难题，真正做到“再也不怕回文字符串的dp了”！

相关文章推荐

发表评论

最热文章

关于作者

  • 被阅读数
  • 被赞数
  • 被收藏数
活动
咨询