問題
状態DP
本問題の場合、atcoderという文字列に一致する部分文字列の数を探すのだが、
全探索をすれば$O(n^7)$かかる。
ここで$N$は入力文字列、$n$はNの長さ、$S="atcoder"$である。
そこで次のように考える。
$N[i]$までの文字を使って$S[j]$までの文字列を作る通りの数は
① $N[i-1]$までの文字を使って$S[j]$までの文字列を作る通りの数 + $N[i-1]$までの文字を使って$S[j-1]$までの文字列を作る通りの数（N[i]=S[j]）
② $N[i-1]$までの文字を使って$S[j]$までの文字列を作る通りの数（N[i]!=s[j]）
例. N="attcoder", S="atcoder"とする
N[i=1]までの文字（a,t）を使ってS[j=0]までの文字列（a）を作る通りの数は1。これは
N[i=0]までの文字（a）を使ってS[j=0]までの文字（a）を作る通りの数1と等しい。
→②のパターン
N[i=1]までの文字（a,t）を使ってS[j=1]までの文字列（at）を作る通りの数は1。これは
N[i=0]までの文字（a）を使ってS[j=1]までの文字（at）を作る通りの数0とN[i=0]までの文字（a）を使ってS[j=0]までの文字（a）を作る通りの数1の和と等しい。
→①のパターン
N[i=2]までの文字（a,t,t）を使ってS[j=1]までの文字列（at）を作る通りの数は2。これは
N[i=1]までの文字（a,t）を使ってS[j=1]までの文字（at）を作る通りの数1とN[i=1]までの文字（a,t）を使ってS[j=0]までの文字（a）を作る通りの数1の和と等しい。
→①のパターン
ここで$DP[i][j]$を$N[i]$までの文字を使って$S[j]$までの文字列を作る通りの数とすれば
$DP[i][j]=\begin{cases}
DP[i-1][j-1] + DP[i-1][j] & s.t.N[i]=S[j] \\\\\
DP[i-1][j] & s.t.N[i]\neq S[j]
\end{cases}
$
といった漸化式に書き表せます。
つまり、$N[n]$までの文字を使って$S[7]$までの文字列（atcoder）を作る通りの数$DP[n][7]$
は$O(7\times n)$で求まります。（下の例では厳密には$O(8(n+1))$）
このようにある時点での状態が前の時点の状態によって決まるような構造に着目したアルゴリズムを状態DPと呼びます。
以下にN="attcoderer"としたときのDPの値の変化を載せます。
-
初期設定
-
i=1を埋める
-
i=3を埋める
-
最終的に
