给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

解法一：暴力解法

列举所有情况需要O(n^2)，判断是否回文需要O(n)，所以暴力解法的时间复杂度是O(n^3)

解法二：动态规划

动态规划有两类题

  • 计算某一个状态
  • 统计多个状态

此题属于统计多个状态，定义i, j为子串范围，S[i, j]为子串
定义P(i, j)
image.png
状态转移方程：
image.png
边界条件（当n=1和n=2时）：
image.png
具体做法：按长度遍历所有情况，取回文长度最大值为结果
动态规划优化了判断回文时的时间复杂度

解法三：中心扩展

动态规划的变体，遍历的方式不一样，从每一个字符向两边扩展，不需要O(n)的额外空间