書き直したのでこっちを読んで: https://kimiyuki.net/blog/2019/02/11/dp-itself/

概要

  • 競プロ界隈で使われている「DP」「動的計画法」という単語は特殊な気がする
  • 集合や関係の言葉で説明されてるのあまり見ないので多様性のため置いておく
  • 整理すると理解が進む(気がする)

動的計画法の定義

例えばWikipedia 動的計画法 - Wikipedia によると以下。 その出典はアルゴリズムイントロダクション 第3版とのこと。

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。

  1. 分割統治法：部分問題を解き、その結果を利用して、問題全体を解く
  2. メモ化：部分問題の計算結果を再利用する

日本オペレーションズ・リサーチ学会というところのWiki 動的計画 - ORWikiで説明されるのは以下のようなもの。

多変数最適化問題の目的関数が再帰性(可分性)と単調性をもち, 制約条件に逐次性があるとき, 再帰式 を導いて, これを１変数ずつ解いて最後に与問題の最適解を求めようとする方法を, 動的計画(dynamic programming)と呼ぶ. 原理としては (i) 最適性の原理 (principle of optimality), (ii) 不変埋没原理(principle of invariant imbedding), (iii) 因果律の原理(principle of causality), の三つに基づく.

大学の授業で買わされた本(その授業の先生が書いた本だった)には、以下のようにある。

動的計画法 (dynamic programming) は、Bellmanによって1950年代に開発された最適化計算の枠組みであり、いわゆる「最適性の原理」に基づいて計算の効率を高めることが主眼となっている。

また、最適性の原理については以下のように書かれている。

最適性の原理: 最適方策では、中間の状態がなにであっても、最適方策の前半部分(後半部分)が、最初の状態からその状態を得る方策(その状態から最終状態に至る方策)のうちで最適である。

まとめよう。 動的計画法とは(個々のアルゴリズムではなくて)アルゴリズムのクラスで、数学的に厳密な定義は持たない。 あるアルゴリズムが動的計画法と呼ばれるのは、元の問題を(元の問題を含むような)部分問題の集合に切り分けそれらの間の漸化式を用いて各問題の答えを得るようなアルゴリズムであるとき。 特に、以下のような性質が重要とされる。

  • 元の問題は切り分けた部分問題の集合に含まれる。 (不変埋没原理)
  • 部分問題の答えを用いて他の部分問題の答えを求める。 (漸化式、分割統治法、メモ化、不変埋没原理)
  • 漸化式が用いるのは部分問題の答えのみであって、部分問題の答えの導出方法には依存しない。 (最適性の原理)

ここで、実装の詳細はまったく要求されていないことに注意したい。 ただし実装はほぼ配列かメモ化再帰の$2$択になる。 また、具体的な部分問題への切り分け方などはまったくの自由であるため、それらは経験を用いて頑張って思い付くしかない。

数学の言葉で言い換えてみる。 対象$y$を構成したいときに、集合$X$上で再帰的に定義される関数$f : X \to Y$である値$x_0 \in X$に対し$f(x_0) = y$が示せるようなものを用意し、これにより構成するような手法。 再帰的定義はそのために整礎帰納法を用いるので、$X$には整礎関係が入らねばならない。 関係$R \subseteq X \times X$が整礎関係とは、無限降下列を持たないこと。つまり$x_0, x_1, \dots, x_n, \dots \in X$で$\dots R x_n R \dots R x_1 R x_0$となるようなものが存在しないこと。 (有限なら)そのような関係から自然に定義される有向グラフはちょうどDAG (directed acyclic graph)であり、なお動的計画法の文脈でDAGがときおり言及されるのはこのため。

動的計画法の例

メモ化再帰

メモ化再帰はそのまま動的計画法。 Fibonacci数の計算が典型例。

Dijkstra法

Dijkstra法とは最短経路長を求めるアルゴリズム。 つまり与えられた非負重み付き有向グラフ$G = (V, E)$とその頂点$s, t$に対し$s \to t$有向路の重みの最小値を求める。 時間計算量は特に気にせず、動的計画法になっている部分について説明する。

元の問題$P$は$s \to t$最短経路長であるが、各頂点$v \in V$に対し問題$P_{v,l}$を長さ$l$以下の有向路での$s \to v$最短経路長とし、問題の集合$\mathbb{P} = \{ P_{v,l} \mid v \in V, 0 \le l \le |V| \}$を用意する。 有向路の長さは高々$|V|$までのみ見ればよいので、元の問題$P = P_{t, |V|} \in \mathbb{P}$となっている。 漸化式は$P_{s,0} = 0$かつ$P_{v,0} = \infty$ for $v \ne s$ および $P_{v,l+1} = \min \{ P_{v,l} + \mathrm{cost}(w \to v) \mid (w \to v) \in E \}$ である。 これは$P_{v,l} \lt P_{w,l+1}$ for all $v, w \in V, \; 0 \le l \lt |V|$という整礎な関係$\lt \subseteq \mathbb{P} \times \mathbb{P}$の上で計算できる。

$s \to w$最短経路長から辺$w \to v$を使って$s \to v$最短経路長を計算するとき、$s \to w$最短経路の具体的な構成にはまったく依存せず単にその問題の答えである経路長のみを用いていることに注意。 これがまさに最適性の原理である。

CYK法

文脈自由言語の構文解析手法。 部分文字列$s$が非終端記号$A$から生成されるかを部分問題$P_{s,A}$とし、Chomsky標準形で書かれた文脈自由文法の規則から自然に導かれる漸化式に従ってこれを決定していくもの。

動的計画法の実装技法の分類

メモ化再帰

最も素直な実装方法である。 ただし定数倍遅い。

利点:

  • 実装が楽
    • 整礎関係の形状が分かりにくくても単に漸化式を書き下せば実装になる。
  • 部分問題の集合$\mathbb{P}$の全体を計算しなくても原問題が求まる場合は、不要な部分を計算しなくてよいので速い。
    • ただし競プロではそのような場合はあまり多くない

欠点:

  • 遅い
    • 関数呼び出しのoverhead
    • キャッシュミスが増える
    • SIMD並列化がなされない
    • データ構造を利用して計算量を落とすのが難しい
  • 空間効率が悪い
    • mapやunordered_mapにメモするときはoverhead

配るDP

実装テク。形がなからず変わるので、場合によってはさらに変形することで計算量が落ちる。

漸化式が使って$y = a_0x_0 + a_1x_1 + \dots + a_{n-1}x_{n-1}$の形だとする。 ここで加法$+$は可換なmonoidとする。 問題の答え$x_0, x_1, \dots, x_{n-1}$が全て求め終わってからこれらを舐めて集計し$y$を求めるのではなく、 $y = 0$と初期化しておいて問題の答え$x_i$が確定した時点でそれぞれ$y \gets y + a_ix_i$と更新することで計算する手法。

計算量が落ちるというのは、例えば$x_i$が定まったとき$x_j$ for $j \in [l_i, r_i)$のそれぞれに$a_ix_i$足すなどの形に変化しているとき。 この場合は一様加算なのでsegment木で$O(N)$から$O(\log N)$にできる。 また、漸化式/整礎関係の形状の計算に時間がかかる場合に、この配るDPにすれば解決する場合もあるだろう。

一般には、単なる実装の形の違いであり通常の形と本質的な差はない。

例題: https://beta.atcoder.jp/contests/arc056/tasks/arc056_d

貰うDP

配るDPに対して、漸化式に従って素直に計算するDPをこう呼ぶ。

bit-DP

実装が楽になるテク。 部分問題集合を何らかの集合$X$の羃集合$\mathbb{P} = \mathcal{P}(X)$とし、整礎関係として包含関係$\subseteq$を用いたときに使われる。 集合$X$を整列しをbitで表わし($\{ x_0, x_2, x_3 \}$と$13 = 2^0 + 2^2 + 2^3$を対応させる) $|X| = n$として以下のようにループを回すと、部分集合$s$について見ているときに$t \subseteq s$な部分集合$t$すべてについて計算が済んでいるという性質がある。 これを使うDPのこと。

    vector<int> dp(1<<n);
    for (int s = 0; s < (1<<n); ++ s) {
        ...
        dp[s] = ...;
        ...
    }

例題: https://beta.atcoder.jp/contests/tdpc/tasks/tdpc_ball

区間DP

問題を区間に分割して解くもの。有名な例としてはCYK法など。

swapするやつ (名前不明)

空間計算量を削減する手法。 部分問題の集合が直積$A \times B$の形をしていて整礎関係が辞書式順序のようになっているときに、空間計算量を$O(|A| |B|)$から$O(|B|)$にできる。

例えば表がint dp[1000][1000];のようになるがdp[i+1]の各要素を計算するのにdp[i]の要素だけが分かっていればよいとき、int dp[2][1000];と宣言してdp[(i+1)&1]とdp[i&1]の間で計算をすれば十分。これのこと。

以下のようにやるのがおすすめ。

    vector<int> cur(n);
    vector<int> prv;
    repeat (i,n) {
        cur.swap(prv);
        cur.clear();
        cur.resize(n);
        ...
    }

圧縮による怪しげな高速化をするやつ (名前不明)

部分問題に上手く切り分けられなかったときに無理矢理計算する手段。

対象の問題設定で素直な状態があるとする。 例えばゲームの必勝手番を求めるとして、ゲームの状態遷移がDAGになっているとき。 そのような状態と遷移をそのまま部分問題と漸化式にしてしまうことはできる。 しかしこれは単なる全列挙であり、まだ足りない場合は多い。 ここで最適性の原理に注目して、状態のうち今後の遷移に関係しない部分は情報を落としてしまい上手く状態をまとめることで高速化できる。

例題: https://beta.atcoder.jp/contests/arc074/tasks/arc074_c

参考資料