给出一个字符串，其中包括3种字符: ‘(‘, ‘)’, ‘?’.其中?表示这个字符可以是’(‘也可以是’)’. 现在给出字符串S,你可以在’?’处填写’(‘ 或者 ‘)’，当然随意填写得到的序列可能是括号不匹配的。例如”(?”，如果你填写’(‘那么”((“是括号不匹配的！ 现在你的任务是确定你有多少种填写方案，使得最终的字符串是括号匹配的！2种方案是不同的，当2种方案中至少存在1个填写字符是不同的。 例如，对于”((??))”,我们可以得到2种方案: “((()))”, “(()())”。
数据包含多组测试数据第一行输入一个字符串S(S的长度不超过16)。
输出一个整数,表示合法的填写方案数。
思路：可以用搜索做，这个题目数据很小，但是要是字符串长度为1000呢？？？那么就考虑dp吧。首先，它有三种状态，'(' ')' '?' 那么可以用dp[i][j]表示历遍到第i个字符，没有匹配的'('有j个的情况下的种数......那么题目就可以转化为，在历遍len个字符，没有匹配的'('有0个的情况下的种数.....dp[len][0]
对应状态，'（'——dp[i][j]=dp[i-1][j-1] 在第i个字符为'('的情况下，种数就等于上一状态i-1个字符，j-1个'('的种数
')'——dp[i][j]=dp[i-1][j+1] 第i个字符为')'的时候，为匹配的')'肯定要-1，所以推导状态就是前一个未-1的状态
'?'——dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[1005][1005],len;
char a[1005];
int main()
{
while(scanf("%s",a)>0)
{
memset(dp,0,sizeof(dp));
dp[0][1]=1;
len=strlen(a);
//for(int i=0;i<len;i++)
//printf("%c",a[i]);
for(int i=1;i<len;i++)
{
for(int j=0;j<len;j++)
if(a[i]=='(')
dp[i][j]=dp[i-1][j-1];//%1000000007;
else if(a[i]==')')
dp[i][j]=dp[i-1][j+1];//%1000000007;
else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]);//%1000000007;
}
printf("%d
",dp[len-1][0]);
}
return 0;
}