最长回文子串

前段时间太忙所以就断更了，尽量从今天开始继续每日一更。

最长回文子串

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

方法一：动态规划法

①分解子序列。若要s[i]到s[j]为回文串的话，那么需要s[i+1]到s[j-1]为回文串并且s[i]==s[j]。那么我们就需要将s[i+1]到s[j-1]是否为回文串以及回文串的长度做出记录。

②基例。若“aba”的情况的话与我们分解子序列的求法是一致的，但是“aa”这样的情况的话显然去使用分解子序列的求法就会有问题，所以我们就需要单独处理这样子的基例。

③为了记录s[i]到s[j]的回文长度，那么我们需要一个二维数组，A[i][j]表示s[i]到s[j]的回文长度，若不是则为0。

方法二：中心扩展法

思路：回文串本身就是中点为中心左右对称的，所以这里可以以每一个字符为中心寻找回文串，但需要注意一点，如果回文串为偶数的话，那么他的对称中心在两字符之间，所以在中心扩展时需要把两字符之间也加入进来。故需要进行n+n-1次的中心扩展。