题解 | #括号区间匹配#

解题思路：

• 令$d{p}_{i,j}dp\_\{i,j\}$表示从下标$i\to ji\; \backslash to\; j$的最小需要补充的符号数，即区间中不匹配的括号数。初始化 $d{p}_{i,i}=1dp\_\{i,i\}\; =\; 1$ 则有状态转移方程$d{p}_{i,j}=d{p}_{i+1,j-1}+match(i,j)\mathrm{，}\mathrm{匹}\mathrm{配}\mathrm{为}0\mathrm{，}\mathrm{不}\mathrm{匹}\mathrm{配}\mathrm{为}2dp\_\{i,j\}\; =\; dp\_\{i+1,j-1\}\; +\; match(i,j)，匹配为0，不匹配为2$。
• 枚举$k,k=i\to j-1k,\; \backslash \; k\; =\; i\; \backslash to\; j-1$。$d{p}_{i,j}=\min (d{p}_{i,j},d{p}_{i,k}+d{p}_{k+1,j})dp\_\{i,j\}\; =\; \backslash min(dp\_\{i,j\},dp\_\{i,k\}\; +\; dp\_\{k+1,j\})$
• 输出答案$d{p}_{0,len-1}dp\_\{0,len-1\}$

#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
string s;
int match(int x, int y){
    return ((s[x] == '[' && s[y] == ']') || (s[x] == '(' && s[y] == ')'))? 0: 2;
}
int main(){
    cin>>s;
    int len = s.size();
    for(int i = 0; i < len; ++i) dp[i][i] = 1;
    for(int ln = 2; ln <= len; ++ln){
        for(int i = 0; i < len; ++i){
            int j = i + ln - 1 ;
            if(j >= len) break;
            dp[i][j] = dp[i+1][j-1] + match(i, j);
            for(int k = i; k < j; ++k){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    cout<<dp[0][s.size()-1]<<endl;
    return 0;
}