最长回文子串

题目：给你一个字符串s， 找到s中最长的回文子串。
解法：动态规划
令dp[i][j] 表示字符串s的下标i到j 构成的子串s[i:j] 是否为回文串。则有
dp[i][j] = dp[i+1][j-1] && (s[i]==s[j])

此外，注意在状态转移方程中，是从长度较短的字符串向长度较长的字符串进行转移，因此要注意动态规划的循环顺序。

string longestPalindrome(string s) {
    int n = s.length();
    if (n == 0) return "";

    bool dp[n][n];
    int res = 1;
    string resStr = s.substr(0, 1);

    for (int i=0; i<n; i++) {
        dp[i][i] = true;
        if (i+1 < n) {
            dp[i][i+1] = (s[i]==s[i+1]);
            if (dp[i][i+1]) {
                res = 2;
                resStr = s.substr(i, 2);
            }
        }
    }

    for (int L=2; L<=n; L++) {
        for (int i=0; i<n+1-L; i++) {
            int j = i + L - 1;
            if (s[i] == s[j]) {
                if (i+1 <= j-1) dp[i][j] = dp[i+1][j-1];
            } else {
                dp[i][j] = false;
            }
            if (dp[i][j]) {
                int cnt = j - i + 1;
                if (cnt > res) {
                    res = cnt;
                    resStr = s.substr(i, cnt);
                }
            }
        }
    }
    return resStr;
}