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

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

示例 1：

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

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

 

动态规划解法----引自力扣题解　

　　为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

我们给出 P(i,j)  的定义如下：

 

　　这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…

复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(n^2)

 

class Solution {
public:

    string longestPalindrome(string s) {
        bool dp[1001][1001];  //dp[i][j]表示 i...j 的字串是否为回文串
        string ans="";
        int left=0,right=-1;
        int len=s.length();
        //vector<bool>  dp[1001];
        for(int i=0;i<len;i++){
            memset(dp[i],0,sizeof(dp[i]));  //运行环境的坑
            dp[i][i]=true;
            if(right-left+1<1){
                right=left=i;
            }
            if(i+1<len && s[i]==s[i+1]){
                dp[i][i+1]=dp[i+1][i]=true;
                if(dp[i][i+1]  && right-left+1<(i+1-i+1)){
                    left=i;
                    right=i+1;
                }
            }
        }
        
        for(int j=2;j<len;j++){
            for(int i=0;i+j<len;i++){        
                dp[i][i+j]= (s[i]==s[i+j] && dp[i+1][i+j-1]);
                
                if(dp[i][i+j] && right-left+1<(i+j-i+1)){
                    left=i;
                    right=i+j;
                }
            }
        }

        if(right==-1)return "";
        else return s.substr(left,right-left+1);
    }
};