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

括号就能使这个字符串的所有括号左右配对。"/>

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

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

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));}
}