题解 | #密码截取#

import java.util.Scanner;


import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        // Scanner in = new Scanner(System.in);

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        // 注意 hasNext 和 hasNextLine 的区别
        //最长回文字符串 动态规划
        String s = in.readLine();
        char[] chars = s.toCharArray();
        System.out.print(F(chars));

    }

    //主函数
    public static int F(char[] chars){

        return dpProcess(chars);
    }

    public static int process(char[] c,int L,int R){

        if(L==R){
            return 1;
        }

        if(L==R-1){
            if(c[L]==c[R]){
                return 2;
            }else{
                return 1;
            }
        }

        //对于普遍位置
        //L位置和R位置的字符不相同,但是L位置或者R位置在回文字符串里面
        int ans = 0;
        int p1 = process(c,L,R-1);
        int p2 = process(c,L+1,R);
        int p3 = c[L]==c[R]?process(c,L+1,R-1)+2 : process(c,L+1,R-1);
        ans = Math.max(Math.max(p1,p2),p3);
        return ans;
    }

    //改dp
    public static int dpProcess(char[] chars){
        int N = chars.length;
        int[][] dp = new int[N][N];

        dp[N-1][N-1] = 1;
        for(int i=0;i<N-1;i++){
            dp[i][i] = 1;
            dp[i][i+1] = chars[i] == chars[i+1] ? 2:1;
        }

        
        for(int i = N-3;i>=0;i--){
            for(int j=i+2;j<N;j++){

                int p1 = dp[i][j-1];
                int p2 = dp[i+1][j];
                int p3 = (chars[i] == chars[j]  && dp[i+1][j-1]== j-i-1)?(dp[i+1][j-1]+2):dp[i+1][j-1];
                dp[i][j] = Math.max(Math.max(p1,p2),p3);
            }
        }
     
        return dp[0][N-1];


    }


}