最长回文子串

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

思路：可以采用动态规划的方法，其中dp[i][j]表示s第i到j位置组成的子串是否为回文子串，则更新方程就是dp[i][j] = dp[i+1][j-1], if s[i] == s[j]，为了可以这样更新，遍历的时候要注意只需遍历上半三角即可

class Solution {
public:
    string longestPalindrome(string s) {
        int sz = s.size();
        if (sz < 2) {
            return s;
        }

        vector<vector<int>> dp(sz, vector<int>(sz, 1));
        int maxLen = 1;
        int beg = 0;
        for (int j = 1; j < sz; ++j) {
            for (int i = 0; i < j; ++i) { //注意只需要遍历对角线上面的值
                if (s[i] != s[j]) {
                    dp[i][j] = 0;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

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