注意: この文章を読んでも「DP」ができるようにはなりません

主張

DP (Dynamic Programming, 動的計画法) とは、うまく再帰的に定義された関数からそれをいい感じに計算するアルゴリズムを得る変換のことである。

説明

DPを説明するために区別すべき対象は以下の4つである。

  1. 問題
  2. 再帰的な関数
    • ただし、数学的な意味での関数
  3. アルゴリズムの高レベルの記述
    • 特に今回の説明においては「具体的な計算量を持つもの」である
    • 以下、単に「アルゴリズム」と呼ぶ
  4. アルゴリズムの実装レベルの記述
    • 以下、単に「コード」と呼ぶ

これらの間の関係は以下のようになる。

image/svg+xml帰着実装変換「問題を解く」問題P(y)実装int dp[N][M];再帰的な関数f : X → Yアルゴリズム(1)(3,4)(5)(6)(2)

さて、DPはこの図の頂点や辺で言うとどれであるだろうか。 これを考えると、その要素の多くが「DP」と呼ぶことができることに気付くだろう。 それらを列挙するとおよそ以下のようになる。

  1. 問題を再帰的な関数を計算する問題に帰着させる変換としての「DP」
    • 「なにを状態とすればいいか分からなくて上手くDPできなかった」などと言うときの「DP」はこれ
  2. 再帰的な関数からそれを適当な計算量で計算するアルゴリズムを得る変換としての「DP」
    • 「DPをするには最適性の原理が必要で $\dots$」などと言うときの「DP」はこれ
  3. アルゴリズムの分類としての「DP」
    • 「Dijkstra法はDPである」などの主張の「DP」はこれ
  4. 具体的なひとつのアルゴリズムの名前としての「DP」
  5. アルゴリズムをコードに落とす実装手法としての「DP」
    • この「DP」はよく「メモ化再帰」と対比される
  6. これらの過程をまとめた総称としての「DP」
    • 「DPやるだけで解けるよ」などと言うときの「DP」はこれ

これらのどれも広義のDPとしてよいだろうが、そのうちどれが狭義のDPとしてふさわしいだろうか。 まず「5. 実装手法としてのDP」は明らかに適切ではなく、「6. 総称としてのDP」は間違いでないとしても曖昧であるため拒否されるべきである。 「4. 具体的なアルゴリズムの名前としてのDP」は間違いである。 例えばKruskal法と呼ばれるべき具体的なアルゴリズムはちょうどひとつであるが、DPはそのようなちょうどひとつのアルゴリズムであるとは思えない。 もしそうなのだとしたらDPそのものには何か具体的な計算量が定まっているべきであるが、そうでない。 次に「1. 関数への帰着としてのDP」は、重要でありかつ実際の運用における最大の難しさだが、DPそのものであるとは思えない。 なぜなら、DPは計算量と関連する何かであるはずだがこの変換は計算量とは無関係であるためである。

よって「2. アルゴリズムへの変換としてのDP」と「3. アルゴリズムの分類としてのDP」が残る。 どちらもDPそのものであると考えて不足はないように思える。 さて前者、後者、その両方のいずれを選ぶべきだろうか。 前者の立場でDPそのものを定義しようとすれば「DPとは再帰的に定義された関数からそれを計算するアルゴリズムを得る変換のことである」などとなり、後者の立場でDPそのものを定義しようとすれば「DPとは再帰的に定義された関数から得られたいい感じのアルゴリズムの総称である」などとなる。 ここで後者の立場での定義は前者の変換の概念を含む表現になってしまう。 もしこの変換の概念に触れずに説明をしようとすれば必然的に「再帰的に定義された関数」などの概念もその説明に含めることができなくなる。 補足で述べるように DAG を用いて説明をしてもよいため「再帰的に定義された関数」という文字列そのものが含まれる必要はないが、やはり DAG や最適性の原理などのほとんど等価な概念は必要である。 よって前者の「アルゴリズムへの変換としてのDPのみがDPである」という立場と両方を選ぶ「アルゴリズムへの変換としてのDPとそのようにして変換されたアルゴリズムの総称としてのDPの両者がDPである」という立場のふたつが残る。 しかしこのふたつを比較するならば後者を含めるかはどちらでもよいということになり、含めても含めなくてもよいようなものがDPそのものであるとは考えられない。 このことから、アルゴリズムへの変換としてのDPこそがDPそのものであると言える。 よって冒頭の主張が従う。

具体例

Typical DP Contest: D - サイコロ を使って具体例を見ていこう。

まず「サイコロを \(N\) 回振ったとき、出た目の積が \(D\) の倍数となる確率を求めよ」は問題である。 これはほとんどそのままと言っていいだろう。 あるいは「関数 \(f(d, n) = \#\left\{ \omega : \dot{n} \to 6 \mid \prod _ {i \lt n} \omega(i) \equiv 0 \pmod{d} \right\} / 6^n\) の値を計算せよ」と理解してもよいだろう。 ただし自然数 \(n\) に対し集合 \(\{ 0, 1, 2, \dots, n - 1 \}\) を \(\dot{n}\) と書くとする。

この問題を再帰的に定義された関数を計算することに帰着させよう。 サイコロの目が \(1, 2, 3, 4, 5, 6\) のみであることから \(D = 2^A \cdot 3^B \cdot 5^C\) と書けるとしてよい。 ここで性質「\(f(n, a, b, c)\) の値は、サイコロを \(n\) 回振ったとき、出た目の積の素因数に \(2\) が\(a\) 回以上含まれかつ \(3\) が\(b\) 回以上含まれかつ \(5\) が\(c\) 回以上含まれる確率に等しい」を満たすような関数 \(f : \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{Q}\) を考える。 そのような \(f\) が存在するとすれば \(f(N, A, B, C)\) の値は問題の答えである。 さてここで以下の定義式

\[f(n, a, b, c) = \begin{cases} 1 & (n = 0 \land a = b = c = 0 \;\text{のとき}) \\ 0 & (n = 0 \land \lnot (a = b = c = 0) \;\text{のとき}) \\ \frac{1}{6} \cdot \left( \begin{array}{l} f(n - 1, a, b, c) \\ + f(n - 1, \max(0, a - 1), b, c) \\ + f(n - 1, a, \max(0, b - 1), c) \\ + f(n - 1, \max(0, a - 2), b, c) \\ + f(n - 1, a, b, \max(0, c - 1)) \\ + f(n - 1, \max(0, a - 1), \max(0, b - 1), c) \end{array} \right) & (n \ge 1 \;\text{のとき}) \\ \end{cases}\]

は目的の性質を満たす \(f\) に対する再帰的定義を与える。 再帰の各ステップで引数の自然数 \(n\) の大きさが真に減少するため定義に循環はなく、正しく定義できていることが分かる。 このように定義されたことにより関数 \(f\) は存在しかつ計算可能であることが分かった。 しかしこの定義はそれを計算するときの計算量については何も言及していないことに注意しなければならない。

そして次に、上で定義された関数 \(f\) を計算するアルゴリズムを考えよう。 単純には、その再帰的定義に従ってそのまま計算をすればよい。 これは時間計算量 \(O(6^N)\) かつ空間計算量 \(O(N)\) のアルゴリズムである。 しかしこれでは計算量が大きすぎる。 ここでDPを用いると時間計算量 \(O(N A B C)\) かつ空間計算量 \(O(N A B C)\) あるいは \(O(A B C)\) などのアルゴリズムが手に入る。 今回の主張に従うと、この \(O(N A B C)\) のアルゴリズムはDPそのものではなく、このアルゴリズムを得る操作こそがDPである。

最後にこのアルゴリズムを実装してコードを得る。 ここでは配列とループを使ってもよいし、メモ化再帰を用いてもよい。

補足: 語の分析

変換される対象としての出現する再帰的な関数の引数のことを「状態」と呼ぶとする。

  • 「bit DP」「桁 DP」「木 DP」
    • 状態によるDPの分類
  • 「inline DP」「全方位木DP」「配るDP」
    • DPによって得られたアルゴリズムをさらに加速させる変換のこと。あるいはアルゴリズムの分類
  • 「貰うDP」
    • 「配るDP」と対比しての表現

補足: 「DAG上の最短経路」という表現との関係

他のDPの説明との比較を見ておくことは必要だろう。

関数 $f : X \to Y$ が再帰的に定義されるためには整礎関係 $R \subseteq X \times X$ が必要である。 整礎関係とは「拡張された数学的帰納法ができるような」「循環も無限後退も起こらない」順序のことである。 整礎ならば DAG であるのでこれを用いれば、状態をDAG の頂点と対応させて「DPはDAG上の最短経路」と説明できる。 DAG ならば整礎という向きは偽であるが、競技プログラミングの文脈ではその反例は滅多に出現しないため、これらは区別されないことは多い。

DAG という説明は具体性があって分かりやすく、間違いではない。 しかし DAG を持ち出すと厳密さが損なわれやすく「1. 関数への帰着としてのDP」「2. アルゴリズムへの変換としてのDP」「3. アルゴリズムの分類としてのDP」がたいていまったく区別されない。そのような説明は完全なものとは言えないだろう。

補足: 「DP」は何が難しかったのか

「適切な関数への帰着」の部分が難しかった。しかしこれはDPそのものではないため、DPそのものは難しくないと分かった。

もちろん適切な関数への帰着が難しいという問題はほとんど手付かずのまま残っている。 しかし混乱が整理されたためにいくらかましにはなっただろう。 このように整理されたことにより、例えば配列とループを用いた実装とメモ化再帰との区別がまったく無意味であることや、状態が \(N \times M\) などの格子状に並ぶ必然性はなかったことが理解できる。