牛客网牛牛数括号（DP）

最新推荐文章于 2022-05-07 01:39:29 发布

ToRe.

最新推荐文章于 2022-05-07 01:39:29 发布

阅读量1.1k

点赞数 1

分类专栏： ----------动态规划----------- 文章标签：动态规划

本文链接：https://blog.csdn.net/j2_o2/article/details/87971817

版权

----------动态规划----------- 专栏收录该内容

14 篇文章

订阅专栏

题目连接

题意

题干已经说的很清楚
给你两个括号序列，不保证合法，求有多少种不同的方法可以将两个括号序列合并成一个合法的括号序列
合并的时候不能改变各自序列原先的顺序

思路

dp[i][j] 表示s1串前i个和s2串前j个，左括号大于等于右括号，还有机会变成合法括号序的方案数。
pre[i][j] 左括号表示+1右括号-1，s1和s2的前缀和。

最后检查一下是否pre[len1][len2] 为0即可，0表示合法。
滚动数组优化空间否则会MLE

代码

#include <bits/stdc++.h>
using namespace std;

char s1[2505], s2[2505];
int dp[2][2505], pre[2][2505], mod = 1e9+7;

int main()
{
    scanf("%s%s",s1+1,s2+1);
    int len1 = strlen(s1+1), len2 = strlen(s2+1), cur = 0;
    dp[cur][0] = 1;
    for(int i = 0; i <= len1; ++i)
    {
        if(i) cur ^= 1;
        if(i) memset(dp[cur], 0, sizeof(dp[cur]));
        for(int j = 0; j <= len2; ++j)
        {
            if(i == 0 && j == 0) continue;
            if(j) pre[cur][j] = pre[cur][j-1] + (s2[j] == '(' ? 1 : -1);
            else pre[cur][j] = pre[cur^1][j] + (s1[i] == '(' ? 1 : -1);

            if(pre[cur][j] < 0) continue;
            if(i) dp[cur][j] += dp[cur^1][j];
            if(j) dp[cur][j] += dp[cur][j-1];
            dp[cur][j] %= mod;
        }
    }
    if(pre[cur][len2] == 0) printf("%d\n",dp[cur][len2]);
    else printf("0\n");
    return 0;
}