最长回文子串

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

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路分析:
解法有很多, 本文用的动态规划.
动态规划就是将一个大问题分解成多个有关联的小问题, 从而得出大问题的答案.
比如 我们要知道 s[i], 到 s[j] 是不是一个回文串, 就要知道 s[i + 1] 到 s[j - 1] 是不是一个回文串.
如果 s[i + 1] 到 s[j - 1] 是一个回文串, 那只要 s[i] == s[j], s[i], 到 s[j] 就是一个回文串.
什么情况下 s[i + 1] 到 s[j - 1] 必是一个回文串呢? 字串的长度小于等于2(不包括0)的时候必是回文串
从而我们可以得到一个公式 dp[i + 1][j - 1] = j - 1 - ( i + 1) < 2
若 j - 1 - ( i + 1) < 2 即 j - i < 3 的 时候, s[i + 1] 到 s[j - 1] 必是一个回文串
理清这些后, 此题就没有什么难度了
代码如下:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2)
            return s;
        int begin = 0, maxLen = 1;
        //生成一个 n x n 的二维数组
        vector > dp(n, vector(n));
        // 初始化对角线
        for(int i = 0; i < n; i++)
        {
            dp[i][i] = 1;
        }
        for(int j = 1; j < n; j++)
        {
            for(int i = 0; i < j; i++)
            {
                //判断dp[i][j] 是不是回文串的判断公式
                if(s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1] == 1))
                {
                    dp[i][j] = 1;
                }

                if(dp[i][j] == 1 && j - i + 1 > maxLen)
                {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};