小A有一个只包含左右括号的字符串S。但他觉得这个字符串不够美观,因为它不是一个合法的括号串。一个合法的括号串是这样定义的:

  1. ()是合法的括号串
  2. 若A是合法的括号串,则(A)则是合法的括号串
  3. 若A,B是合法的括号串,则AB也是合法的括号串。

小A现在希望删掉S中若干个字符,使得剩下的字符串是一个合法的括号串。小A想知道有多少不同的方案。两个方案是不同的,当且仅当他们删除的位置不同。比如当S是(()时,有两种方案。分别是删掉第一个位置,或是删掉第二个位置。

输入格式

第一行一个整数n,代表S的长度。 第二行输入n个字符,字符要么是(,要么是)。代表串S。

输出格式

一行一个整数,代表不同的方案数。答案对10^9+7取模。

数据范围 2 4 6 10

输入样例:

8
)(()(())

输出样例:

30

题目分析

暴力的话应该用栈来做,并且看这个数据范围的话是过不了的,考虑DP。

设 F(i, j) 表示考虑到第 i 个位置,未匹配左括号数量为 j。那么可以枚举上一个位置 i - 1,以及对应的未配对左括号数量 j’

对于 i 位置:

  • 若 i 为右括号,则 j = j’ - 1, 即 未匹配的左括号 - 1
  • 若 i 为左括号,则 j = j’ + 1, 即 未匹配的左括号 + 1

最后的答案就是F(i,0), 即考虑到第i个位置,所以左括号均匹配的情况。

代码实现

#include <iostream>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7, N = 1e4 + 10;

char s[N];
int dp[N][N];
int main() {
    int n;
    cin >> n >> s + 1;
    dp[0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if(s[i] == '(' && j > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]);
            if(s[i] == ')' && j < n) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]);
            dp[i][j]
        }
    }
    cout << dp[n][0] - 1;
    return 0;
}

但是这个代码会爆空间, 那么我们考虑滚动数组优化空间。

#include <iostream>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7, N = 1e4 + 10;

char s[N];
int dp[2][N];
int main() {
    int n;
    cin >> n >> s + 1;
    dp[0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            int I = i & 1;
            dp[I][j] = dp[!I][j];
            if(s[i] == '(' && j > 0) dp[I][j] = (dp[I][j] + dp[!I][j - 1]);
            if(s[i] == ')' && j < n) dp[I][j] = (dp[I][j] + dp[!I][j + 1]);
            dp[I][j]
        }
    }
    cout << dp[0][0] - 1;
    return 0;
}
分类: DPStackString

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status