牛客网2019真题-23-非连续回文字符串

package org.niuke.solution23;


import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        char[] input = s.toCharArray();
        int[][] dp = new int[input.length][input.length];
        for(int r = 0; r < dp.length; r++){
            dp[r][r] = 1;
            for(int l = r - 1; l >= 0; l--){
                if(s.charAt(l) == s.charAt(r)){
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                }else{
                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        System.out.println(dp[0][dp.length - 1]);
    }
}