动态规划解决最长回文子串问题

题目描述：
给定一个字符串s，找到其中最长的回文子串，并返回这个子串。回文串是指正着读和反着读都一样的字符串。子串要求是连续的字符序列。

示例：
输入：s = "babad"
输出："bab" 或 "aba"

输入：s = "cbbd"
输出："bb"

解题过程：

1. 问题分析
   最长回文子串问题有多种解法，暴力法时间复杂度为O(n³)，中心扩展法为O(n²)，而动态规划解法也是O(n²)，但思路更为清晰。我们需要找到一个时间复杂度可接受的解法。

2. 动态规划思路
   定义dp[i][j]为布尔值，表示字符串s从索引i到j的子串（包含i和j）是否为回文串。

   • 当i = j时，单个字符一定是回文串
   • 当j = i+1时，两个字符需要判断是否相等
   • 当j > i+1时，子串s[i:j]是回文串当且仅当：
     1. s[i] = s[j]
     2. 去掉首尾字符后的子串s[i+1:j-1]也是回文串

3. 状态转移方程
   dp[i][j] =

   true,                                  当 i = j
   (s[i] == s[j]),                       当 j = i + 1
   (s[i] == s[j]) && dp[i+1][j-1],       当 j > i + 1
   

4. 算法步骤
   a. 初始化一个n×n的二维数组dp，全部设为false
   b. 初始化最长回文子串的起始位置start=0，长度max_len=1
   c. 处理长度为1的子串：所有dp[i][i] = true
   d. 处理长度为2的子串：检查相邻字符是否相等
   e. 从长度为3开始，逐步增加子串长度，按照状态转移方程计算dp值
   f. 在计算过程中，如果发现更长的回文子串，更新start和max_len
   g. 最后返回s[start:start+max_len]

5. 具体实现细节

   • 由于需要用到dp[i+1][j-1]的值，必须按照子串长度递增的顺序计算
   • 从长度为3开始计算，因为长度1和2的情况已经单独处理
   • 注意数组边界，避免越界访问

6. 时间复杂度与空间复杂度

   • 时间复杂度：O(n²)，需要填充n×n的dp表
   • 空间复杂度：O(n²)，用于存储dp表
   • 可以通过优化（如中心扩展法）将空间复杂度降为O(1)

7. 边界情况处理

   • 空字符串：返回空字符串
   • 单个字符：返回该字符
   • 全部相同字符：返回整个字符串

8. 算法优化
   实际实现时，可以优化空间复杂度：

   • 只存储必要的数据，比如用一维数组滚动更新
   • 使用中心扩展法，空间复杂度为O(1)，但时间复杂度仍为O(n²)

这种方法通过动态规划将大问题分解为小问题，逐步构建出完整的解，是解决最长回文子串问题的一种经典且易于理解的方法。