题目大意
求长度为 nnn 的括号序列 aaa 可能是多少个长度为 mmm 的合法括号序列 bbb 的子序列。
题目思路
读题时需要注意的一个点是括号序列 aaa 不一定是合法的，但求的括号序列 bbb 一定是要合法的。
我们可以将 ( 看成权值为 111 ，将 ) 看成权值为 −1-1−1 ，那么一个合法的括号序列需要满足以下条件：
* 序列和为 000 。
* 最小前缀和为不小于 000 。
我们考虑用动态规划解决这个问题。
设 dpi,j,kdp_{i,j,k}dpi,j,k 表示括号序列 bbb 中已经有 iii 个字符，括号序列 aaa 的前 jjj 个字符是括号序列 bbb 的子序列，括号序列 bbb 的权值前缀和为 kkk 。
那么有以下四种转移：
* i+1i+1i+1 位置为 ( ，且 j=nj=nj=n 或 sj+1≠s_{j+1}\nesj+1 = ( ，则 dpi+1,j,k+1+=dpi,j,kdp_{i+1,j,k+1}+=dp_{i,j,k}dpi+1,j,k+1 +=dpi,j,k 。
* i+1i+1i+1 位置为 ( ，且 j<nj<nj<n 且 sj****_{j+1}=sj+1 = ( ，则 dpi+1,j+1,k+1+=dpi,j,kdp_{i+1,j+1,k+1}+=dp_{i,j,k}dpi+1,j+1,k+1 +=dpi,j,k 。
* i+1i+1i+1 位置为 ) ，且 j=nj=nj=n 或 sj+1≠s_{j+1}\nesj+1 = ) ，则 dpi+1,j,k−1+=dpi,j,kdp_{i+1,j,k-1}+=dp_{i,j,k}dpi+1,j,k−1 +=dpi,j,k 。
* i+1i+1i+1 位置为 ) ，且 j<nj<nj<n 且 sj****_{j+1}=sj+1 = ) ，则 dpi+1,j+1,k−1+=dpi,j,kdp_{i+1,j+1,k-1}+=dp_{i,j,k}dpi+1,j+1,k−1 +=dpi,j,k 。
时间复杂度 O(nm2)O(nm^2)O(nm2) 。
参考代码
