【拼多多2019】括号序列。(DP)

1、题目描述

一个合法的圆括号表达式满足以下条件：

 1.“”空字符串被认为是合法的。
 2.如果字符串“X”与“Y”是合法的，则“XY”也被认为是合法的。
 3.如果字符串“X”是合法的，则“(X)”也是合法的。

例如，“”，“()”，“()()”，“(())”这些都是合法的。

现在给出两个不保证合法的由圆括号组成的字符串，你需要交错这两个圆括号序列（在组成的新字符串中，每个初始字符串都保持原来的顺序）得到一个新的合法的圆括号表达式（不同的交错方式可能得到相同的表达式，这种情况分开计数），求共有多少结果合法的交错方式（无法得到合法的圆括号表达式则输出0），输出结果对109+7取模后的值。

输入格式

输入共两行，每行包含一个由“(”和“)”组成的字符串，长度不超过2500。

输出格式

输出为一个数字，表示合法的交错方式数量对109+7取模后的值。

输入样例：

(()
())

输出样例：

19

2、问题描述：

• 两个字符串序列，包含左右括号，判断能组成多少种合法的组合。

3、问题关键：

• 括号序列：
  1.左括号为+1，右括号为-1，过程中，s >= 0;
  2.结束时：s == 0；
• 最长公共子序列。
  1.f[i][j] = f[i - 1][j] + f[i][j - 1];

4、C++代码：

//括号序列。
//最长公共子序列。
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 2510, mod = 1e9 + 7;

int n, m;
char a[N], b[N];
int as[N], bs[N];
int f[N][N];

void get_prefix_sum(int sum[], char str[], int k)
{
    for (int i = 1; i <= k; i ++ )
        if (str[i] == '(')
            sum[i] = sum[i - 1] + 1;
        else
            sum[i] = sum[i - 1] - 1;
}

int main()
{
    cin >> a + 1 >> b + 1;
    
    n = strlen(a + 1);
    m = strlen(b + 1);
    
    get_prefix_sum(as, a, n);
    get_prefix_sum(bs, b, m);
    
    if (as[n] + bs[m] != 0) puts("0");
    else
    {
        for (int i = 0; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
                if (!i && !j) f[i][j] = 1;
                else
                {
                    if (as[i] + bs[j] >= 0)
                    {
                        if (i) f[i][j] += f[i - 1][j];
                        if (j) f[i][j] += f[i][j - 1];
                        f[i][j] %= mod;
                    }
                }
        
        cout << f[n][m] << endl;
    }
    
    return 0;
}