括号配对

题目描述

Hecy又接了个新任务：BE处理。BE中有一类被称为GBE。
以下是GBE的定义：

空表达式是GBE
如果表达式A是GBE，则[A]与(A)都是GBE
如果A与B都是GBE，那么AB是GBE下面给出一个BE，

求至少添加多少字符能使这个BE成为GBE。

输入描述:

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

输出描述:

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

输入

[])

输出

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 7;
char s[N]; int dp[N][N];
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    memset(dp, 0, sizeof(dp));
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']'))
                    dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
            for (int k = l; k < r; k++) {
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
        }
    }
    cout << n - dp[1][n] << endl;
    return 0;
}

原文链接: https://www.cnblogs.com/HighLights/p/13327046.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367542

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

题目描述

输入描述:

输出描述:

输入

输出

相关推荐