括号序列【第十二届】【省赛】【B组】 DP

思路

设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示到第 i i i个括号，当左括号比右括号多 j j j个的情况下，添加左括号的方案数。首先显然在一堆左括号里添加左括号对方案数是毫无贡献的，因此只有在一堆右括号中加左括号才会对方案产生贡献。则：

• s[i] == '('时， d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i - 1][j - 1] dp[i][j]=dp[i−1][j−1]；
• s[i] == ')'时， d p [ i ] [ j ] = d p [ i − 1 ] [ j + 1 ] + d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] + ⋯ + d p [ i − 1 ] [ 2 ] + d p [ i − 1 ] [ 1 ] dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j] + dp[i - 1][j - 1] + \dots + dp[i - 1][2] + dp[i - 1][1] dp[i][j]=dp[i−1][j+1]+dp[i−1][j]+dp[i−1][j−1]+⋯+dp[i−1][2]+dp[i−1][1]

什么意思？

对于当前 i i i括号为右括号，左括号比右括号多 j j j的情况而言，其状态由 不加(加零个)左括号的方案数(也就是左括号比右括号多 j + 1 j + 1 j+1个的方案数)、加一个左括号的方案数(左括号比右括号多 j j j个的方案数)、…相加得到

但是这样复杂度会跑到 O ( n 3 ) O(n^3) O(n3)，显然跑不动，那么考虑优化：

容易发现右括号时候的式子类似斐波那契的式子，可以改为递推式： d p [ i ] [ j ] = d p [ i − 1 ] [ j + 1 ] + d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] + ⋯ + d p [ i − 1 ] [ 2 ] + d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 0 ] d p [ i ] [ j − 1 ] = d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] + ⋯ + d p [ i − 1 ] [ 2 ] + d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 0 ] → d p [ i ] [ j ] = d p [ i − 1 ] [ j + 1 ] + d p [ i ] [ j − 1 ] dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j] + dp[i - 1][j - 1] + \dots + dp[i - 1][2] + dp[i - 1][1] + dp[i - 1][0]\\ dp[i][j - 1] = dp[i - 1][j] + dp[i - 1][j - 1] + \dots + dp[i - 1][2] + dp[i - 1][1] + dp[i - 1][0]\\ \rightarrow dp[i][j] = dp[i - 1][j + 1] + dp[i][j - 1] dp[i][j]=dp[i−1][j+1]+dp[i−1][j]+dp[i−1][j−1]+⋯+dp[i−1][2]+dp[i−1][1]+dp[i−1][0]dp[i][j−1]=dp[i−1][j]+dp[i−1][j−1]+⋯+dp[i−1][2]+dp[i−1][1]+dp[i−1][0]→dp[i][j]=dp[i−1][j+1]+dp[i][j−1] 优化完毕！

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 5010, MOD = 1e9 + 7;
int dp[N][N];

inline int calc(string s){
    int len = s.size();
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 1; i