DPに対するメモ - すていさんの雑記

最近JOI(日本情報オリンピック)の存在を知り、過去問を解いたりしていたのだが、おそらくDP的な考え方を使う問題を解いた。¹

DPは前の値を使って次の値を計算できるか、次の値を計算するときにはその前の値がすべて計算終了していなければいけない。

例えば再帰関数は必要になれば自分自身を呼び出し前の値を計算する。
一度計算した値を保存しておき、無駄な計算を省いたメモ化再帰を用いた場合、DPとほぼ同じになる。
これはDPにおいても再帰においても、現在の値を計算するのに必要な前の値はすでに計算が終わっているからだ。

巨大な問題を解くのに、そのまま解くのではなく、再帰的な部分問題に分割し、小さなものから前の結果を利用して解いていく。

DPテーブルの添え字は状態を表しているので、
DP[状態1][状態2] = その時点での最良
としてやるといい？のかな？