题解 | #括号区间匹配#

JavaScript题解，ACM模式，之前刷到过差不多的题

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    while ((line = await readline())) {
        match(line)
    }
})();

function match(s) {
    if (s.length <= 1) {
        return 1;
    }
    const sArr = s.split("");
    let dp = new Array(s.length)
        .fill(Array(s.length).fill(-Infinity))
        .map((val, idx) => {
            return val.map((el, _idx) => {
                if (idx === _idx) {
                    return 1;
                } else if (_idx > idx) {
                    return -el;
                } else {
                    return null;
                }
            });
        });
    // console.log(dp);
    for (let i = 1; i < s.length; i++) {
        for (let j = 0; j < s.length - i; j++) {
            if (
                (sArr[j] === "(" && sArr[j + i] === ")") ||
                (sArr[j] === "[" && sArr[j + i] === "]")
            ) {
                dp[j][j + i] = Math.min(dp[j][j + i], dp[j + 1][j + i - 1]);
            }
            for (let k = j; k < j + i; k++) {
                dp[j][j + i] = Math.min(
                    dp[j][j + i],
                    dp[j][k] + dp[k + 1][i + j]
                );
            }
        }
    }
    // console.log(dp);
    console.log(dp[0][s.length - 1])
    return dp[0][s.length - 1];
}