分析
问题：统计字符串SSS（只含 ( 和 ) ）的所有子序列中，合法括号序列的数量（含空串），答案对10910^9109取模。n≤2000n \le 2000n≤2000。
关键观察：一个子序列是合法括号序列，当且仅当：
1.
长度是偶数2k2k2k
2.
前kkk个字符全是 ( ，后kkk个全是 )
DP 设计：设f[i][j]f[i][j]f[i][j]表示考虑前iii个字符，当前已选子序列中有jjj个未匹配的 ( 的方案数。
不选 S[i]S[i]S[i]：f[i][j]+=f[i−1][j]f[i][j] \mathrel{+}= f[i-1][j]f[i][j]+=f[i−1][j]
选 S[i]S[i]S[i]：
若S[i]=(：f[i][j]+=f[i−1][j−1]S[i] = ( ：f[i][j] \mathrel{+}= f[i-1][j-1]S[i]=(：f[i][j]+=f[i−1][j−1]（多了一个未匹配左括号）
若S[i]=)：f[i][j]+=f[i−1][j****[i] = ) ：f[i][j] \mathrel{+}= f[i-1][j****[i]=)：f[i][j]+=f[i−1][j+1]（匹配掉一个左括号）
最终答案为f[n][0]f[n][0]f[n][0]（所有左括号都被匹配）。
验证：S=))(()(S = ))(()(S=))(()(
空串：1 种
() ：选位置3,43,43,4或3,63,63,6，共 2 种
总计 3 ✓✓✓
复杂度：O(n2)O(n^2)O(n2)，n≤2000n \le 2000n≤2000完全可行。
代码：
验证：
样例1：))(()())(()())(()(，答案f[6][0]=3✓f[6][0] = 3 ✓f[6][0]=3✓
样例2：34 个字符，17 个 ( 后 17 个 ) ，答案333606220333606220333606220（可用代码验证）
说明：
f[i][j]f[i][j]f[i][j]中jjj最大为iii（前iii个字符最多选iii个左括号），内层循环到iii即可
用滚动数组将空间从O(n2)O(n^2)O(n2)降到O(n)O(n)O(n)
答案包含空串（f[0][0]=1f[0][0] = 1f[0][0]=1的转移路径）
