题意解读

题目说一个字符串中由3种字符组成：（，）和？
当这一位是问号时，可以是 ( 和 ) 中的一种，问一共有多少种方案使得最后满足 括号字符串的条件。

思路

一般看到这种方案数的问题，都用 dp 做。需要列出转移式子。

我们看到这题就会想，可不可以用dp记录当前在第i的位置能不能有j个左括号和k个右括号

于是!

dp[i][j][k]诞生了。可是该怎么优化呢？我们要手动模拟一下，寻找方法。

不难发现：

一个字符串是合法括号序列，当且仅当满足以下条件：

从左到右扫描字符串时，任意时刻已经出现的右括号数量都不超过左括号数量；
扫描完整个字符串后，左括号数量与右括号数量相等。

也就是j>=k
于是就可以用j-k作为第二维。刚好

S 是一个长度不超过 3000 的非空字符串

所以N方能过。

完整代码

#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
string s;
long long dp[3005][3005];
int main(){
	cin>>s;
	int n=s.size();
	s=" "+s;
	dp[0][0]=1;//还没有开始计算，左括号和右括号数量之差为0
	for(int i=1;i<=n;i++){
		if(s[i]=='('){
			for(int j=1;j<=n;j++){//只能从dp[i-1][j-1]上一项，差值比现在小转移过来
				dp[i][j]=dp[i-1][j-1];
				dp[i][j]%=mod;
			}
		}else if(s[i]==')'){
			for(int j=0;j<=n;j++){
				dp[i][j]=dp[i-1][j+1];//只能从dp[i][j+1]转移过来，因为只看作右括号
				dp[i][j]%=mod;
			}
		}else{
			for(int j=0;j<=n;j++){
				if(j==0){//在这以一位只能从dp[i-1][j+1]转移过来，因为j-1越界了
					dp[i][j]+=dp[i-1][j+1];//转移
					dp[i][j]%=mod;
				}else{
					dp[i][j]+=dp[i-1][j-1];//原理同上
                    dp[i][j]%=mod;
					dp[i][j]+=dp[i-1][j+1];
					dp[i][j]%=mod;
				}
			}
		}
	}
	cout<<dp[n][0];//注意看，题目中说道括号字符串的定义
	return 0;
}

总结

遇到这类题可以从题目给的数据范围入手，特别是方案数、可行性、最多的字眼。