题解 | #括号区间匹配#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int match (String s) {
        // write code here
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                if ((s.charAt(i) == '(' && s.charAt(j) == ')') || (s.charAt(i) == '[' &&
                        s.charAt(j) == ']')) {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        return dp[0][len - 1];
    }
}

1. 初始化: 定义dp[i][j] 表示子串 s[i...j] 所需的最小添加括号数。对于每个单个字符的子串（即 i == j 的情况），dp[i][i] = 1，因为任何一个独立的左括号或右括号都需要一个对应的括号来匹配。
2. 计算dp数组: 倒序遍历，开始填充 dp 数组。外层循环倒序遍历字符串的每个字符作为子串的起点 i，内层循环正序遍历从 i + 1 开始的字符作为子串的终点 j。初始化 dp[i][j] 默认值为Integer.MAX_VALUE，便于求最小值。
3. 状态转移方程: 对于每个子串 s[i...j]，检查字符 s[i] 和 s[j] 是否构成一对匹配的括号。如果是，那么 dp[i][j] 可以从 dp[i+1][j-1] 获得，因为两端的括号已经匹配，我们只需要考虑它们之间的部分。如果 s[i] 和 s[j] 不匹配或者字符之间不构成括号对，那么考虑所有可能的分割点 k，将子串 s[i...j] 分为两部分 s[i...k] 和 s[k+1...j]。dp[i][j] 是所有分割点中 dp[i][k] 加上 dp[k+1][j] 的最小值。
4. 返回结果: 在完成 dp 数组的填充后，dp[0][len - 1] 包含整个字符串 s 所需添加的最小括号数。