Longest Palindromic Substring 最长回文子序列

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"
           

解法一：

对于字符串str，假设dp[i,j]=1表示str[i…j]是回文子串，那个必定存在dp[i+1,j-1]=1。这样最长回文子串就能分解成一系列子问题，可以利用动态规划求解了。构造状态转移方程

上面的状态转移方程表示，当str[i]=str[j]时，如果str[i+1…j-1]是回文串，则str[i…j]也是回文串；如果str[i+1…j-1]不是回文串，则str[i…j]不是回文串。

初始状态

dp[i][i]=1

dp[i][i+1]=1 if str[i]==str[i+1]

上式的意义是单个字符，两个相同字符都是回文串。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() < 2) return s;
        int dp[s.size()][s.size()] = {0};
        int maxlen = 1;
        int start = 0;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; j <= i; j++){
                if(i - j < 2)
                    dp[j][i] = (s[i] == s[j]);
                else
                    dp[j][i] = (s[i] == s[j] && dp[j + 1][i - 1]);
                if(dp[j][i] && maxlen < i - j + 1){
                    maxlen = i - j + 1;
                    start = j;
                }
            }
        }
        return s.substr(start, maxlen);
    }
};