Day32.

1070. 括号配对

Hecy 又接了个新任务：BE 处理。

BE 中有一类被称为 GBE。

以下是 GBE 的定义：

空表达式是 GBE如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE如果 A 与 B 都是 GBE，那么 AB 是 GBE

下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。

注意：BE 是一个仅由(、)、[、]四种字符中的若干种构成的字符串。

输入格式

输入仅一行，为字符串 BE。

输出格式

输出仅一个整数，表示增加的最少字符数。

数据范围

对于所有输入字符串，其长度小于100。

输入样例： []) 输出样例： 1 动态规划：

定义状态：

dp[i][j]表示字符串s[i···j]变成GBE所需的最少添加字符数。

初始化：

dp[i][i] = 1，单个字符只需添加一个字符就能成为GBE。

状态转移：

如果 s[i] 和 s[j] 是匹配的括号对（即 s[i] == '(' && s[j] == ')' 或 s[i] == '[' && s[j] == ']'），则 dp[i][j] = dp[i+1][j-1]。否则，要在 s[i...j] 中找到一个点 k，使得 dp[i][j] = dp[i][k] + dp[k+1][j] 最小。

结果：

返回dp[0][n-1]即为将字符串变成GBE所需的最少添加字符数。 代码： #include <climits> #include <iostream> #include <string> #include <vector> using namespace std; int minAdd(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; i++) { dp[i][i] = 1; // 长度为1时，只需添加一个 } for (int m = 2; m <= n; m++) {//遍历字符串长度 for (int i = 0; i + m - 1 < n; i++) {//从起点遍历到终点 int j = i + m - 1; dp[i][j] = INT_MAX;//初始化为最大值 if ((s[i] == '(' && s[j] == ')') || (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]); } } } return dp[0][n - 1]; } int main() { string s; cin >> s; int result = minAdd(s); cout << result << endl; return 0; }

细节解释：

如果 dp[i][j] 没有被初始化为 INT_MAX，而是初始化为 0，则可能出现：

dp[i][k] + dp[k+1][j] 的最小值大于0，而 dp[i][j] 初始值为 0，那么程序会错误地认为最小值是 0。