题解 | #密码截取#

dp[j][i] = 1代表从j到i的子串是回文串

一共三种情况的

• j == i , 说明只有一个字符，一定是回文
• i-j == 1 说明只有两个字符，此时如果str[i] == str[j], 说明一定是回文串
• i-j > 1 说明有两个以上的字符，这时候，如果str[i] == str[j] , 那么就可以从第一种或者第二种情况转移过来，当dp[j+1][i-1] = 1的时候， 这就代表dp[j][i]也是1

这样dp就可以转移过来，然后在算dp的过程当中顺便用i-j+1来算出每次回文串的长度，然后取最大值

#include <iostream>
using namespace std;


const int maxn = 2500+10;
int dp[maxn][maxn];


int main() {
    int ans = -1;

    string str;
    cin >> str;
    int len = str.size();
    for(int i = 0; i < len ; i++){
        for(int j = i; j >= 0; j--){
            if(i == j){
                dp[j][i] = 1;
                ans = max(ans, i-j+1);
            } 
            else if(i-j == 1 && str[i] == str[j]) {
                dp[j][i] = 1;
                ans = max(ans, i-j+1);
            }
            else if(str[i] == str[j] && dp[j+1][i-1] == 1){
                dp[j][i] = 1;
                ans = max(ans, i-j+1);
            }
        }
    }

    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")