这道题比较特殊，答案不是dp数组的某个值，而是记录下来的一个变量
主要思路是二维DP数组，用i、j存储两个下标，如果input[i] = input[j]&&dp[i - 1][j - 1]==1 那么 dp[i][j] = 1 ，然后初始化dp[i][i]就行了
patzjujztaccbcc

代码

  1. #include<algorithm>
  2. #include<stdio.h>
  3. #include<cstring>
  4. #include<iostream>
  5. using namespace std;
  7. const int maxn = 1010;
  8. int dp[maxn][maxn]={0};
  9. char input[maxn];
  11. int main(){
  12.     scanf("%s", input);
  13.     int len = strlen(input), ans = 1;
  14.     for(int i = 0; i < len; i++){
  15.         dp[i][i] = 1;
  16.         if(i < len - 1){
  17.             if(input[i] == input[i + 1]){
  18.                 dp[i][i + 1] = 1;
  19.                 ans = 2;
  20.             }
  21.         }
  22.     }
  23.     //一定要把1和2先处理掉，从3开始
  24.     for(int L = 3; L <= len; L++){//长度为1和2的都已经被处理了
  25.         for(int i = 0; i + L - 1 < len; i++){
  26.             int j = i + L -1;
  27.             if((input[i] == input[j]) && (dp[i + 1][j - 1] == 1)){
  28.                 dp[i][j] = 1;
  29.                 ans = L;
  30.             }
  31.         }
  32.     }
  33.     printf("%d", ans);
  34.     return 0;
  35. }