括号匹配

这道题不同于LC921. 使括号有效的最少添加，这里是两种括号。

dp,f[i][j]表示从i位到j位的序列变为合法序列最少添加多少个字符。
如果匹配st[s]与st[e]匹配，那么f[s][e] = f[s + 1][e - 1];否则f[s][e] = f[s][k] + f[k + 1][e];
需要从右下角，并且从左往右数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            System.out.println(leastKuohao(line));
        }
    }

    public static int leastKuohao(String s) {
        int n = s.length();

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int i = 0; i < n - 1; i++) {
            dp[i][i+1] = isMatch(s.charAt(i), s.charAt(i+1)) ? 0 : 2;
        }

        for (int start = n - 1; start >= 0; start--) {
            for (int last = start + 2; last < n; last++) {
                int min1 = Integer.MAX_VALUE;
                if (isMatch(s.charAt(start), s.charAt(last))){
                    min1 = dp[start + 1][last - 1];
                }
                // 注意这里不能用else，两端匹配的情况下，也可能用分成两半的更小。
                int min2 = Integer.MAX_VALUE;
                for (int i = start; i < last; i++) {
                    min2 = Math.min(min2, dp[start][i] + dp[i+1][last]);
                }

                dp[start][last] = Math.min(min1, min2);
            }
        }

        return dp[0][n-1];
    }

    public static boolean isMatch(char c1, char c2) {
        return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']');
    }