题解 | #括号区间匹配#

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }

        int min;
        for (int i = 1; i < len; i++) { // i 区间长度
            for (int j = 0; j < len - i; j++) {
                if (match(s.charAt(j), s.charAt(j + i))) {
                    min = dp[j + 1][j + i - 1];
                } else {
                    min = Integer.MAX_VALUE;
                }
                for (int k = j; k < j + i; k++) {
                    min = Math.min(min, dp[j][k] + dp[k + 1][j + i]);
                }
                dp[j][j + i] = min;
            }
        }
        System.out.println(dp[0][len - 1]);
    }
    

    private static boolean match(char left, char right) {
        return left == '(' && right == ')'
                || left == '[' && right == ']';
    }
}