题目描述

两种思考方式。

import java.io.*;
public class Main {
    static int N;
    static char c[];
    public static void main(String[] args) throws IOException {  // * 如果 A 与 B 都是 GBE，那么 AB 是 GBE   比密码脱落多了这个条件，不一定回文。
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String s = cin.readLine();
        N = s.length();
        c = new char[s.length()+1];
        for(int i = 1;i<=N;i++){
            c[i] = s.charAt(i-1);
//            System.out.println(c[i]);
        }
        dp2();
    }

    static void dp1(){  //dp即答案。
        int[][] dp = new int[N+1][N+1];  //将lr 变成合法 方案的数的最小值。
        for(int i = 1;i<=N;i++) dp[i][i] = 1;
        for(int len = 1;len<=N;len++){
            for(int l = 1;l+len <=N; l++){
                int r = l+len;
                dp[l][r] = 0x3f3f3f3f; //求这个的时候赋值为最大,因为求的最小值
                //凑回文类型。
                if(check(c[l],c[r]))  dp[l][r] = dp[l+1][r-1];  //都在匹配中
                dp[l][r] = Math.min(dp[l][r],dp[l][r-1]+1);
                dp[l][r] = Math.min(dp[l][r],dp[l+1][r]+1);
                dp[l][r] = Math.min(dp[l][r],dp[l+1][r-1]+2);
                //凑AB
                for(int k = l;k<r;k++){  //枚举分界点。
                    dp[l][r] = Math.min(dp[l][r],dp[l][k]+dp[k+1][r]);
                }

            }
        }
        System.out.println(dp[1][N]);
    }

    static void dp2(){ // 和密码脱落一样反向思考，求序列里面满足的最大子序列，然后剩下的个数即是需要添加的个数
        int[][] dp = new int[N+1][N+1];  //lr 里面合法的子序列长度
//        dp[0][0] = 1; //
//        for(int i = 1;i<=N;i++) dp[i][i] = 1;
        for(int len = 1;len<=N;len++) {
            for (int l = 1; l + len <= N; l++) {
                int r = l + len;
                //左边匹配 回文型.
                if(check(c[l],c[r])) dp[l][r] = Math.max(dp[l][r],dp[l+1][r-1]+2);
                dp[l][r] = Math.max(dp[l][r],dp[l+1][r]);
                dp[l][r] = Math.max(dp[l][r],dp[l][r-1]);
                dp[l][r] = Math.max(dp[l][r],dp[l+1][r-1]);
                //右边AB型最多子串。
                for(int k = l;k<r;k++){  //枚举分界点。
                    dp[l][r] = Math.max(dp[l][r],dp[l][k]+dp[k+1][r]);
                }
            }
        }
        System.out.println(N-dp[1][N]);
    }

    static boolean check(char a,char b){
        if(a=='(' && b==')') return true;
        if(a=='[' && b==']') return true;
        return false;
    }
}