TopCoder SRM 686 Div1 Easy BracketSequenceDiv1

朝回なので出なかったけど、1WAしたので出なくてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14210

問題

丸括弧・角括弧で構成される文字列Sがある。
この部分文字列のうち、括弧の対応が正しく取れたものが何通りあるか答えよ。

なお、部分文字列が一緒でも、抽出した位置が違うものは別と見なす。

解法

最初半分全列挙風に書いたらTLEした。
dp(L,R) := S[L..R]に対し、題意を満たす部分文字列の数、とする。

S[L..R]中で最初に取る括弧の対応をS[x],S[y]とする。
すなわちS[x]は開き括弧でS[y]は対応する閉じ括弧である。まだS[x]以前の括弧は一度も取らない。
その場合、S[(x+1)..(y-1)]及びS[(y+1)..R]がそれぞれ括弧の対応が正しいならS[L..R]が条件を満たすので、
で計算できる。

ll dp[51][51];

class BracketSequenceDiv1 {
	public:
	int N;
	string S;
	
	ll dpdp(int L,int R) {
		if(L>=R) return 1;
		if(dp[L][R]>=0) return dp[L][R];
		
		int i;
		dp[L][R]=dpdp(L+1,R);
		for(i=L+1;i<=R;i++) {
			if((S[L]=='(' && S[i]==')') || (S[L]=='[' && S[i]==']')) dp[L][R] += dpdp(L+1,i-1)*dpdp(i+1,R);
		}
		return dp[L][R];
	}
	
	long long count(string s) {
		N=s.size();
		S=s;
		MINUS(dp);
		
		return dpdp(0,N-1)-1;
	}
}

まとめ

この正しい括弧列、なんかいい名前を決めてほしいな。
問題によって説明の仕方がバラバラで面倒。