给定一个由 [’, ]’, ( ,‘)’组成的字符串,请问最少插入多少个括号就能使这个字符串的所有括号左右配对。

给定一个由 [’, ]’, ( ,‘)’组成的字符串,请问最少插入多少个括号就能使这个字符串的所有括号左右配对。例如当前串是([[])”,那么插入一个]即可满足。

import java.util.*;
public class Main{
    public static int process(String str){
        char[]ch=str.toCharArray();
        int n=ch.length;
        int[][]dp=new int[n][n];
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }
        for(int i=1;i<n;i++){
            for(int j=0;j+i<n;j++){
                dp[j][j+i]=Integer.MAX_VALUE;
                if((ch[j]=='('&&ch[j+i]==')')||(ch[j]=='['&&ch[j+i]==']'))
                    dp[j][j+i]=Math.min(dp[j][j+i],dp[j+1][j+i-1]);
               for(int k=j;k<j+i;k++){
                   dp[j][j+i]=Math.min(dp[j][j+i],dp[j][k]+dp[k+1][i+j]);
               }
            }
        }
        return dp[0][n-1];
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String str=sc.next();
        System.out.print(process(str));
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29