IJPC2012 Practice A - 国際情報オリンピック日本代表プログラミングコンテスト

http://ijpc2012pr.contest.atcoder.jp/tasks/ijpc_ijpc

問題

ある文字列Sが与えられる。Sの部分文字列に「IJPC」という4文字が現れるように文字を書き換えたい。
ここでの部分文字列とは、0文字以上の任意の文字を削除して得られる文字列を、元の文字列の部分文字列と呼ぶ。
例えば「IAMJAPLJ」の場合は、最後の2つのLかJをCに書き換えればよい。
最小の書き換え回数を答える。

考え方

dp。

dp["IJPC"のそれぞれの文字][i] = i文字目までで"IJPC"それぞれの文字の最低書き換え回数。
dp[j][i] = min(dp[j-1][i-1] + i文字目がjと同じなら0それ以外なら1, dp[j-1][i]);