区间dp2

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Scanner;
/**
 * 给定一个由 '[' ，']'，'('，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。
 * 例如当前串是 "([[])"，那么插入一个']'即可满足。
 *
 * ([[])
 * 1
 */
public class 区间dp {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int[][] dp=new int[s.length()][s.length()];
        //dp[i][j]表示在i，j区间上需要添加的最小的括号数量。
        for(int i=0;i<s.length();i++){
            dp[i][i]=1;
        }
        int min;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<s.length()-i;j++){
                if((s.charAt(j)=='('&&s.charAt(i+j)==')')||(s.charAt(j)=='['&&s.charAt(i+j)==']')){
                    min=dp[j+1][i+j-1];
                }else{
                    min=Integer.MAX_VALUE;
                }
                for(int k=j;k<i+j;k++){
                    min=Math.min(min,dp[j][k]+dp[k+1][i+j]);
                }
                dp[j][i+j]=min;
            }
        }
        System.out.println(dp[0][s.length()-1]);
    }
}