Typical DP Contest I-イウィ

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi
　このコンテストの中では楽なほうだと思います……。
　iとwのみからなる文字列Sからiwiを取りのぞける最大の回数を求めよ、という問題。
　dp[i][j] := 半開区間i <= k < j からiwiを取りのぞける回数の最大値
とします。ある区間全部が消せる場合、そのとなりが両端がiw + ... + i または　i + ... + wiのかたちならこれも消せます。というのをメモ化再帰してあげると区間が小さい方から計算してくれます。

string s;
int dp[301][301];//半開区間i ~ jでiwiを除去できる回数の最大
int dfs(int f, int t){
    if(dp[f][t] != -1) return dp[f][t];
    if(t - f <= 2) return dp[f][t] = 0;
    int m = t - f - 3;
    for(int k = f + 1; k < t; k++)
      dp[f][t] = max(dp[f][t], dfs(f, k) + dfs(k, t));
    if(s[f] == 'i' && s[f + 1] == 'w' && s[t - 1] == 'i' && dfs(f + 2, t - 1) * 3 == m)
      dp[f][t] = max(dp[f][t], dp[f + 2][t - 1] + 1);
    if(s[f] == 'i' && s[t - 2] == 'w' && s[t - 1] == 'i' && dfs(f + 1, t - 2) * 3 == m)
      dp[f][t] = max(dp[f][t], dp[f + 1][t - 2] + 1);
    return dp[f][t];
}
int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, s.size()) << endl;
    return 0;
}

　メモ化再帰の問題はきれいに書けるので好きです。普通にループを回したほうがメモリ効率が良いことのほうが多いですが……。再帰は命令がレジスタに乗る回数が増えるのがオーバーヘッドになって遅いとも聞きますしね。