SRM411 Div2 500

問題

暗号化した文字列をやり取りする。有効な文字列validWordsが与えられ、文字列にはそれぞれが0回以上現れる。そして、文字列中の文字をそれぞれ入れ替える時、元と違う個数だけコストがかかる。たとえば、"abc"が有効な文字列ならば"acb"はコストが2、"bca"はコストが3など。並び替えた文字列を複数並べることで暗号化した文字列を作る。
ある文字が与えられる時、合計コストが最小のもののコストを返す。

考え方

文字列のiでの最小コストでdp。
dp[i+valid[j].length()] = min(dp[i+valid[j].length()], dp[i]+cost);