题目描述
定义一个合法的括号序列
- 空序列合法
- 如果S合法，那么(S)和[S]合法
- 假设A和B合法，那么AB合法
合法序列 - ()，[]，(())，([])，()[]，()[()]
非法序列 - (，[，]，)(， (])，([()，([)]
给定一个序列，求最少添加多少个括号，才能得到一个合法序列。
输入描述
输入仅一行，为一个字符串,
输出描述
输出只有一个整数，表示增加的最少字符数。
测试用例
输入
[])
输出
1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 200
#define INF 0x3f3f3f3f3f3f3f3f
ll dp[MAXN][MAXN];
string s;
int main() {
cin >> s;
ll n = s.size();
for (ll i = 1; i <= n; i++)
dp[i][i] = 1;
for (ll l = 2; l <= n; l++)
for (ll i = 1; i <= n - l + 1; ++i) {
ll j = l + i - 1;
dp[i][j] = INF;
for (ll k = i; k <= j - 1; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
if ((s[i - 1] == '(' && s[j - 1] == ')') || (s[i - 1] == '[' && s[j - 1] == ']'))
dp[i][j] = min(dp[i + 1][j - 1], dp[i][j]);
}
cout << dp[1][n];
return 0;
}