「NowCoder」括号

题目大意：给出一个长度为 $n$ 的括号序列，可以删除若干个字符使得该括号序列合法，问有多少种不同的删除方案？答案对 $1e9+7$ 取模。$n \le 10000$

可以将原问题转化成：求该序列有多少个合法的子串。

设 $f[i][j]$ 表示前 $i$ 个位置所选的子串中有 $j$ 个未匹配的左括号的方案数，有状态转移方程：

$$f[i][j]=\begin{cases} f[i-1][j]+f[i-1][j-1], & s[i]=\text{'('}\\ f[i-1][j]+f[i-1][j+1], & s[i]=\text{')'} \end{cases}$$

其中 $f[i-1][j]$ 表示 $i$ 位置不选的情况。

DP数组的第一维可以化简掉。

#include <cstdio>

const int N = 10005, P = 1e9+7; 
int f[N], n; char s[N];

int main() {
	scanf("%d%s", &n, s);
	f[0] = 1;
	for (int i = 0; i < n; ++i) {
		if (s[i] == '(')
			for (int j = i + 1; j; --j) f[j] = (f[j] + f[j-1]) % P;
		else
			for (int j = 0; j < i; ++j) f[j] = (f[j] + f[j+1]) % P;
	}
	printf("%d\n", (f[0] - 1 + P) % P); //减去空串的方案
	return 0;
}

时间复杂度 $O\left(\dfrac{n(n+1)}{2}\right)$