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

示例 1：

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

示例 2：

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

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() == 0) return "";
        bool dp[1000][1000] = {{false}};
        int max = 0;
        string ans;
        for (int x = s.length(); x >= 0; x--) {
            for (int y = x; y < s.length(); y++) {
                if (y - x < 2) {
                    dp[x][y] = s[x] == s[y];
                } else {
                    dp[x][y] = dp[x + 1][y - 1] && (s[x] == s[y]);
                }
                if (dp[x][y] && y - x + 1 > max) {
                    max = y - x + 1;
                    ans = s.substr(x, y - x + 1);
                }
            }
        }
        return ans;
    }
};

第i到第j个char能否构成回文取决于
1.第i+1到第j-1个char是否回文
2.第i个char和第j个char是否相同
dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]
注意考虑串为空的特殊情况
x自大到小，y从小到大，确保dp[x+1][y-1]已经完成定义

https://leetcode-cn.com/problems/longest-palindromic-substring/