投稿
  1. 首页
  2. C

code • 2022-4-12 • C • 阅读 59

第1张

出错原因分析：

1.

 

2.dp[0][0]=1;

3.

 代码：

#include 
#include
#define N 2010
//#define INF 1e9+7
#define INF 1000000007
using namespace std;
int n;
string s;
int dp[N][N];   //前i个字符中还有j个(需要匹配的答案的数量
int main()
{
    cin>>n>>s;
    s.insert(0," ");
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='('||s[i]=='?')
        {
            for(int j=1;j<=i;j++)
                dp[i][j]+=dp[i-1][j-1]%INF;
        }
        if(s[i]==')'||s[i]=='?')
        {
            for(int j=0;j<=i;j++)
                dp[i][j]+=dp[i-1][j+1]%INF;
        }
    }
    cout<

题目：

给定一个长度为n的括号序列，有些位置确定了，有些位置没有确定，未确定的位置用?表示，求合法括号序列有多少。


一个合法括号序列满足下列条件：

1.（）是合法的括号序列

2.若 S 是合法的括号序列，那么SS,(S)也是合法的括号序列

输入格式:

第一行输入一个正整数n(1≤n≤2000)

第二行输入一个长度为n的字符串，表示括号序列。


数据保证字符串只由(,),?组成。


输出格式:

输出一个非负整数表示答案对 109+7 取模的结果。


输入样例1: 
4
(??)
输出样例1: 
2

给定字符串可能形成下面两种合法的括号序列
(())
()()

输入样例2: 
5
?????
输出样例2: 
0
输入样例3: 
6
(????)
输出样例3: 
5

有以下五种情况

((()))
(()())
()()()
(())()
()(())

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/585076.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表（0条）

保存