动态规划

最长回文子串

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

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/

string longestPalindrome(string s) {
    int m = s.size();
    if (m == 0) {
        return "";
    }
    vector<vector<int>> dp(m, vector<int>(m, 0));
    int start = 0;
    int length = 1;

    for (int i = 0; i < m; i++) {
        // 单个字符属于回文，例如 abcd
        dp[i][i] = 1;

        // 连续两个字符相同属于回文，例如 abb
        if (i < m - 1) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                start = i;
                length = 2;
            }
        }
    }

    for (int len = 2; len <= m; len++) {
        for (int i = 0; i < m - len; i++) {
            int j = i + len;
            // 扩展长度
            if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
                dp[i][j] = 1;

                if (j - i + 1 > length) {
                    start = i;
                    length = j - i + 1;
                }
            }
        }
    }

    return s.substr(start, length);
}