题解 | 括号区间匹配

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else if (i < j) {
                    dp[i][j] = Integer.MAX_VALUE;
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                int minVal = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) {
                    if (dp[i][k] != Integer.MAX_VALUE && dp[k + 1][j] != Integer.MAX_VALUE) {
                        int sum = dp[i][k] + dp[k + 1][j];
                        if (sum < minVal) {
                            minVal = sum;
                        }
                    }
                }

                if (match(s.charAt(i), s.charAt(j))) {
                    int inner = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;
                    if (inner < minVal) {
                        minVal = inner;
                    }
                }

                dp[i][j] = minVal;
            }
        }

        System.out.println(dp[0][n - 1]);
    }

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

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 初始化：二维数组 dp 被初始化为处理不同长度子串的最小插入数。单个字符初始化为1，空子串初始化为0。
2. 处理子串：遍历所有可能的子串长度，从2到整个字符串长度。
3. 分割处理：将子串分割成两部分，计算每部分的最小插入数之和，找到最小值。
4. 配对处理：检查子串的首尾字符是否可以配对，如果可以，则比较中间子串的插入数，更新最小值。