#yyds干货盘点# 动态规划专题：括号区间匹配

1.简述：

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

例如当前串是 "([[])"，那么插入一个']'即可满足。

数据范围：字符串长度满足 

仅一行，输入一个字符串，字符串仅由 '[' ，']' ，'(' ，‘)’ 组成

输出最少插入多少个括号

输入：

([[])

输出：

1

输入：

([])[]

输出：

0

2.代码实现：

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++){//i表示以j为左边界，向右移动的距离。
            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));
    }
}