括号配对

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 945 字

给定含[]的字符串，求最少插入几个字符使其成

一本通
练习

正文

/*
原题：括号配对（GBE，求最少添加多少字符使其合法）
题意：给定含 ()[] 的字符串，求最少插入几个字符使其成为合法括号序列。
思路：区间 DP：dp[i][j] 为区间 [i,j] 配成合法序列的最少插入数；
      若 s[i]s[j] 匹配则 dp=dp[i+1][j-1]，否则枚举断点取 min，单字符为 1。
复杂度：时间 O(L^3)，空间 O(L^2)
易错点：匹配对为 () 或 []；空区间 dp 为 0；需从短区间递推到长区间。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    vector<vector<int>> dp(n+1, vector<int>(n+1,0));
    for(int i=1;i<=n;i++) dp[i][i]=1;
    auto match=[](char a,char b){
        return (a=='('&&b==')')||(a=='['&&b==']');
    };
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=1e9;
            if(match(s[i],s[j])) dp[i][j]=min(dp[i][j], dp[i+1][j-1]);
            for(int k=i;k<j;k++){
                dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]);
            }
        }
    }
    cout<<dp[1][n]<<"\n";
    return 0;
}

括号配对

正文

一本通·提高篇的其它内容