Typical DP Contest I - イウィ

問題

i, wからなる文字列が与えられる。
この文字列から、連続する"iwi"という三文字を取り除く操作が何度でもできる。
操作ができる回数の最大値を求めよ。

制約条件

文字列の長さ≦300

方針

メモ化再帰。
rec2(l, r)を、iwiを余りが出ないように取り除くときの取り除く回数の最大値として、
rec(l, r)を余りが出てもよいので取り除く回数の最大値とする。

rec2(l, r)は、s[l]とs[r]が'i'でなければ0.
'i'だったら、中間の'w'を選び、rec2(l + 1, 'w'の位置-1) + rec2('w'の位置+1, r-1) + 1の最大値が答え。

ソースコード

int rec2(int, int);
 
int n, dp[300][300], dp2[300][300];
string s;
 
int rec(int l, int r){
	if(r - l < 2) return 0;
	int &res = dp[l][r];
	if(res >= 0) return res;
	
	res = max(rec(l+1, r), rec(l, r-1));
	for(int i = l; i < r; i++) res = max(res, rec(l, i) + rec(i+1, r));
	res = max(res, rec2(l, r));
	
	return res;
}
int rec2(int l, int r){
	if(l > r) return 0;
	if(r - l < 2 || s[l] != 'i' || s[r] != 'i') return -inf;
	int &res = dp2[l][r];
	if(res != -1) return res;
	
	res = -inf;
	for(int i = l+1; i < r; i++){
		if(s[i] == 'w') res = max(res, rec2(l+1, i-1) + rec2(i+1, r-1) + 1);
		if(s[i] == 'i') res = max(res, rec2(l, i) + rec2(i+1, r));
	}
	if(res < 0) res = -inf;
	
	return res;
}
int main(){
	cin >> s;
	n = s.size();
	memset(dp, -1, sizeof(dp));
	memset(dp2, -1, sizeof(dp2));
	cout << rec(0, n-1) << endl;
}