题目

c++

回文串，区间DP

class Solution {
public:
    int dp[1005][1005];
    string longestPalindrome(string s) {
        
        int len = s.length();
        
        int ii,jj;
        int m=0;
        
        for(int l=0;l<len;l++)
        {
            for(int i=0;i+l<len;i++)
            {
                int j=i+l;
                
                if(i==j)
                {
                    dp[i][j]=1;
                    if(m<dp[i][j])
                    {
                        m=dp[i][j];
                        ii=i;
                        jj=j;
                    }
                }
                else
                {
                    if(s[i]==s[j])
                    {
      
                        if(i+1<=j-1&&dp[i+1][j-1]!=0)
                        {
                            dp[i][j]=dp[i+1][j-1]+2;
                            if(m<dp[i][j])
                            {
                                m=dp[i][j];
                                ii=i;
                                jj=j;
                             }
                        }
                        else if(i==j-1){
                            dp[i][j]=2;
                            
                            if(m<dp[i][j])
                            {
                                m=dp[i][j];
                                ii=i;
                                jj=j;
                             }
                        }
                        else if(i+1<=j-1&&dp[i+1][j-1]==0)
                        {
                            dp[i][j]=0;
                        }
                    }
                }
            }
        }
        
        string ans="";
        for(int i=0;i<s.length();i++)
        {
            if(i>=ii&&i<=jj)
            ans+=s[i];
        }
        return ans;
    }
};