题解 | #括号区间匹配#

区间dp

dp[i][j]: 区间[i~j]的字符串匹配所插入的字符数最少为dp[i][j]

区间dp，枚举区间长度来遍历i和j。

初始时，区间长度为1时，dp[i][i]=1。长度不为1时，dp[i][j] = inf

当s[i]和s[j]匹配时，dp[i][j] = dp[i+1][j-1]

然后就是枚举区间[i~j]内的分界点，看区间划分的左右两部分的匹配数

#include <iostream>

#include <string.h>
using namespace std;
const int N = 101, inf = 0x3f3f3f3f;
char str[N];
int dp[N][N];
bool check(int l, int r) {
    if ((str[l] == '[' && str[r] == ']') || (str[l] == '(' && str[r] == ')'))
        return true;
    return false;
}
int main() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    for (int d = 1; d <= n; d++) {
        for (int l = 1; l + d - 1 <= n; l++) {
            int r = l + d - 1;
            if (d == 1) dp[l][r] = 1; //仅有一个字符时，那最少插入1个字符才匹配
            else {
                dp[l][r] = inf;  
                if (check(l, r))
                    dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
                //s[l]与s[r]匹配不匹配都要枚举中间的，比如"[]([]" 明显dp[1][5]=1,如果来自于dp[2][4]("](["-明显是3)就不对了
                for (int k = l; k <= r; k++) {
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
                }
            }
            
        }
    }
    printf("%d", dp[1][n]);
    return 0;
}
// 64 位输出请用 printf("%lld")