动态规划解决最长回文子串问题（Longest Palindromic Substring）

问题描述
最长回文子串问题要求在一个给定的字符串中，找到最长的连续子串，使得该子串正序和反序读完全相同（即回文）。例如，字符串 "babad" 的最长回文子串为 "bab" 或 "aba"；字符串 "cbbd" 的最长回文子串为 "bb"。该问题需要高效地确定子串的起始和结束位置，并返回最长回文子串本身。

解题思路
动态规划（DP）通过存储中间结果来避免重复计算。对于最长回文子串问题，我们可以定义状态数组 dp[i][j] 表示子串 s[i:j+1] 是否为回文。通过填充这个二维表，逐步扩展子串长度，最终找到最长的回文子串。

步骤详解

1. 状态定义

   • 设 dp[i][j] 是一个布尔值，表示字符串 s 从索引 i 到 j 的子串是否为回文。
   • 初始条件：所有长度为 1 的子串都是回文（即 dp[i][i] = true）。

2. 状态转移方程

   • 对于长度大于 1 的子串，s[i:j+1] 是回文的条件是：
     • 首尾字符相等：s[i] == s[j]。
     • 去掉首尾后的子串是回文或子串长度不超过 2：
       • 若 j - i <= 2（即子串长度为 2 或 3），只需首尾字符相等即可（例如 "aa" 或 "aba"）。
       • 若 j - i > 2，则需要 dp[i+1][j-1] 为 true。
   • 综合得到转移方程：

     dp[i][j] = true, 当 s[i] == s[j] 且 (j - i <= 2 或 dp[i+1][j-1] == true)
     

3. 填充顺序

   • 由于 dp[i][j] 依赖于 dp[i+1][j-1]（即左下方的值），需要按子串长度从小到大填充。
   • 外层循环遍历子串长度 L（从 2 到 n），内层循环遍历起始索引 i，计算结束索引 j = i + L - 1。

4. 记录结果

   • 在填充过程中，记录最长回文子串的起始位置 start 和长度 max_len。
   • 当 dp[i][j] 为 true 且当前子串长度 L > max_len 时，更新 max_len = L 和 start = i。

5. 复杂度分析

   • 时间复杂度：O(n²)，需要填充 n² 大小的 DP 表。
   • 空间复杂度：O(n²)，用于存储 DP 表。

示例演示
以字符串 "babad" 为例：

1. 初始化：所有长度为 1 的子串为回文（如 dp[0][0] = true）。
2. 长度 L=2：
   • "ba"：s[0]≠s[1] → dp[0][1]=false。
   • "ab"：s[1]≠s[2] → dp[1][2]=false。
   • "ba"：s[2]≠s[3] → dp[2][3]=false。
   • "ad"：s[3]≠s[4] → dp[3][4]=false。
3. 长度 L=3：
   • "bab"：s[0]==s[2] 且 j-i=2 → dp[0][2]=true，更新 start=0, max_len=3。
   • "aba"：s[1]==s[3] 且 dp[2][2]=true → dp[1][3]=true，但长度未超过 3。
4. 继续处理更长子串，最终最长回文子串为 "bab" 或 "aba"。

优化提示

• 实际应用中，Manacher 算法可在 O(n) 时间内解决该问题，但动态规划解法更直观易懂，适合面试中展示基础思路。
• 可优化空间复杂度至 O(n)，仅存储当前和前一行的 DP 状态。