【自留】最长回文子串——动态规划

先看题：

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。

示例 2：

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

思路：如果一个字符串S是回文串，只有在S前后各多一个相同的字符组成的新串S2才会是回文串。因此，采用一个大小为n*n的二维数组来记录每一个s的子串是否为回文（n为s总字符数），用一个二重循环来遍历子串。用数组来记录子串情况能大幅降低重复判断子串是否为回文串的开销，也是动态规划的核心思想。

数组 dp[i][j] 表示下标从 i 到 j 的子串是否为回文串，在最开始需要将所有 i=j 的位置初始化为true，因为单个字符一定是回文串。

循环采用外循环为字符长度，范围[2, n]；内循环为字符串起始位置，范围[0, n)。（选择起点和终点来循环也行）

循环主体：

对于每一个i开始j结束的子串，判断s[i] == s[j]，如果不成立则一定不是回文，对应的dp[i][j]设为false，如果成立，先根据ij的长度判断，如果对应的字符串长度为2，则是回文；长度大于2，则根据dp[i+1][j-1]来记录。

在每一次循环的最后判断该子串长度是否大于之前最长子串，并更新相应变量即可。

细节方面：因为采用了外循环从2开始，循环内会出现的长度最小的字符串为2，对其进行特殊判断即可，如果采用了别的区间或者用i和j作为两层循环，则也需要做对应的边界处理。