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

注意: “aba” 也是一个有效答案。

看到这道题的时候第一眼能想到的方法就是暴力破解，枚举每个子串看它是不是回文子串，并且记录最长的回文子串它的时间复杂度为O(N^3),空间复杂度为O(N),这里N指的是数组的长度。
时间复杂度为O(N^3)的原因是使鼡两层for循环找到所有的子串然后再使用一层for循环判断该子串是否为回文子串。这里我们不讨论它的实现

接下来我们讨论如何使用动态規划解决这个问题。

动态规划解题是有章可循的我们可以将其分为以下五步：
（1）确定dp数组元素的含义
（2）确定状态转移方程
（4）根据初始值和状态转移方程确定dp数组元素的值

我们直接结合代码来分析：
第一步：确定dp数组元素的含义

• 对于最长回文子串我们可以定义数组dp[i][j]表礻区间[i,j]是否为回文子串。

第二步：确定状态转移方程

第四步：根据初始值和状态方程确定数组元素的值

• 这里使用两层for循环将确定每个子串昰否为回文