まずこの問題を考えてみましょう。
文字列S,Tが与えられる。最長共通部分列の長さを求めよ。
これは蟻本にあるようにdp[i][j]:=Sのi字目とTのj字目までの最長共通部分列の長さとすれば良くて
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) (S[i]!=T[j])
dp[i][j] = dp[i - 1][j - 1] + 1 (S[i]==T[j])
でdp tableを更新すれば解くことができます。
では次の問題
文字列S,Tが与えられる。共通部分列の数を求めよ。
これもdp[i][j]:=Sのi字目とTのj字目までの共通部分列の数として
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (S[i]!=T[j])
dp[i][j] = dp[i - 1][j - 1] (S[i]==T[j])
で更新すればいいように思えます。
でもこれではだめで、例えば
S="abc"
T="adc"を考えると
acという共通部分列がdp[3][2]とdp[2][3]から遷移する2通りがあるのでダブルカウントしてしまっていることがわかります。
このように数え上げDPはダブルカウントに気を付ける必要があり、普通のDPよりも難易度が増していることがわかると思います。
それでいろいろ考えていたら、DPってそもそもなんだ?状態とか遷移とかってなんだ?という話になったので、
自分なりに整理してみました。
DPの本質は探索にあって、探索はある操作を行うことで進行します。
操作の定義は簡単で、ある対象に対して何かしらの作用を加えることです。また操作を何回か行って得られたものを結果と定義します。
この際、DPを行える探索は3つの性質を満たしていなければなりません。
1.DAGである。すなわち、有限回の操作で完了する。
期待値DPやゲームDPだと自己ループなどがあったりしますが、結局DAGに帰着できます。
2.求めたいものがある結果に対応している。
つまり求めたいものが探索で網羅できているということです。
3.状態というものがあって、操作の結果はただ一つの状態に属していなければならない。
状態は好きなもので良くて、例えば上の例ではSのi字目とTのj字目でしたが、別にSのi字目だけでも状態になりえます。
ただ一つの状態に属していなければならない、は状態同士が互いに素ということですが、自然な状態を持ってくれば勝手に互いに素になってくれるのでそんな気にしなくていいです。
状態から状態への移り変わりを遷移と定義すると、DPはこの遷移を理解するのがポイントになることがわかると思います。
さっきSのi字目だけを状態にすると、遷移がややこしいことになってDPしにくいです。また１つの状態に求めたいものと求めたくないものが混在していると意味が無いです。このようになんでも状態にはできますが、計算しやすいものは限られています。
ここまでが普通のDPの満たすべき性質ですが、数え上げDPは2を
2'.求めたいものはただひとつの結果と対応する
に変更すればいいです。
例えば最長共通部分列を求めるときは操作を
Sのi字目とTのj字目を見て、等しかったらi+1,j+1に移動して、そうでなければi+1,jまたはi,j+1に移動する
と定義できて、それで全共通文字列を網羅できます。しかし、i,jが異なっていて、i+1,j+1に移動する方法を考えた時、i+1,jに先に移動するか、i,j+1に先に移動するかで求めているものは変わりませんが、結果は2つになっています。よってこれでは数え上げDPができないことがわかります。
では共通部分列の数を求めるときは
i,j以降でS[i']==T[j']となるi',j'に移動するにすれば良いです。計算量はO(|S|^2|T|^2)となりますが、累積和を使えばO(|S||T|)になります。
上の例からわかるように2'は
任意の2つの操作を入れ替えると求めているものが変わる。
に言い換えられます。
このように数え上げDPは遷移が少し複雑になります。計算量を落とす際は累積和を使えばよさそうですね。
一般的な数え上げでも、この操作から考える方法でもれなくだぶりなく数え上げることができます。
二週間ずっと悩み続けた…
