题解 | #密码截取# 动态规划的不同定义的不同解法

#include <iostream>
#include <vector>
using namespace std;

//审题 最长回文子串
//动态规划题解   
//1.确定dp数组
//2. 推导递归的方式
//3.初值与遍历顺序

int main() {
    string str;
    cin>>str;
    
    int n=str.length();
    vector<vector<bool>> dp(n,vector<bool>(n,false));
    int maxlen=1;
/*    //版本1
    for (int i=0; i<n; i++) 
    {
        for (int j=0; j<=i; j++) 
        {
            if(i==j)
                dp[j][i]=true;
            else if ( i-j==1)
                dp[j][i] = (str[i] == str[j]);
            else
                dp[j][i] = (str[i] == str[j] && dp[j + 1][i - 1]);

            if(dp[j][i] && i - j + 1 > maxlen)    
                maxlen=i-j+1;
        }    
    }
*/
//版本2    不同的遍历顺序 导致细节略微有差异   dp [i][j] 表示的是i-j为子串 左边i 右边j  所以上一个包含的子串就为 i+1  j-1
//分为 3个情况  i=j 一个字符的时候 必定为子串
//j-i=1 他们相差一个字符 但是完全相同的情况下 为子串
//j-i>1  之前必须要是子串 且现在边界要相同 才是新的子串
    for (int i=n-1; i>=0; i--) 
    {
        for (int j=i; j<n; j++) 
        {
            if(i==j)
                dp[i][j]=true;
            else if ( j-i==1)
                dp[i][j] = (str[i] == str[j]);
            else
                dp[i][j] = (str[i] == str[j] && dp[i + 1][j - 1]);

            if(dp[i][j] && j - i + 1 > maxlen)    
                maxlen=j-i+1;
        }    
    }


/*
//变种 求最长回文子序列  
// max 
       for (int i = s.size() - 1; i >= 0; i--)
            for (int j = i + 1; j < s.size(); j++)
                if(i==j)
                    dp[i][j]=true;        
                if(s[i]==s[j])
                    dp[i][j]=d[i+1][j - 1]+2    
                else
                dp[i][j]=max(d[i][j - 1],d[i+1][j])
*/
    cout<<maxlen<<endl;
}
// 64 位输出请用 printf("%lld")