第一行一个整数n，代表S的长度。
第二行输入n个字符，字符要么是(，要么是)。代表串S。
一行一个整数，代表不同的方案数。答案对10^9+7取模。
20%: n <= 20
40%: n <= 100
60%: n <= 1000
100%: n <= 10000
动态规划，但是只需要使用一维的DP
dp[j]就意味着还有多少个左括号 也就是‘（’；
原因十分的简单，根据题目要求我们就可以知道，左括号需要和右括号匹配，但是只有一个右括号是没有什么用的。
打个比方 ： （） 就可以成为一个合法的括号串；
）（ 就不可以成为一个合法的括号串。
现在，接着讲DP；
这道题DP的转移方程，就可以看代码了。
关于DP的问题，可以在评论区中问。
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
char ch[10001];
long long dp[10001];
int main()
{
int n;
cin>>n;
cin>>ch;
dp[0]=1;
for(int i=0;i<n;i++)
{
if(ch[i]==‘(‘)
{
for(int j=n-i;j>=0;j--) dp[j+1]=(dp[j+1]+dp[j])%mod;
}
else
{
for(int j=1;j<=n-i;j++) dp[j-1]=(dp[j-1]+dp[j])%mod;
}
}
cout<<((dp[0]-1)+mod)%mod;
return 0;
}
原文：https://www.cnblogs.com/FXY-180/p/9609443.html