DP のイメージ・メンタルモデルに関して

動的計画法 (dynamic programming, DP) はイメージ・メンタルモデルを掴むまでのハードルが中々高いような気がします。

一例を示しますが、必ずしも全部の問題を一貫して説明できるとは限らないので、いくつかのイメージを持っているといいかもしれません（どれかしらに固執する必要はないということ）。

数式がそれなりに出てきますが、苦手な人は深呼吸とかしながら落ちついて読んでもらえるとうれしいです。

数式に関して補足

Python 風な擬似コードで軽く説明しておきます。

$$\sum_{x\in S} f(x)$$

これは、下記の関数の返り値と同じものを表していると思ってください。$\sum$ はシグマ (sigma) と読みます。

def sigma(S, f):
    res = 0
    for x in S:
        res += f(x)
    return res

慣れている人は sum(map(f, S)) だと思っても大丈夫です。

$$\max S$$

これは下記です。

def maximum(S):
    res = -oo  # -∞、すなわちその型の最小値で初期化
    for x in S:
        res = min(res, x)
    return res

慣れている人は、max([-oo, *S]) だと思っても大丈夫です。

$$ \{f(x) \mid x\in S\}$$

これは下記です。

def make_set(S, f):
    res = set()
    for x in S:
        res.add(f(x))
    return res

慣れている人は、set(f(x) for x in S) とか set(map(f, S)) だと思っても大丈夫です。

また、$f(i, j) \triangleq$ ($i$ や $j$ の式) という表記は、左辺の表記を右辺の内容で定義しますよ、という意味です。$f(i, j) \coloneqq \dots$ や $f(i, j) \stackrel{\text{def}}{=} \dots$ などと書く人もいます。

å°Žå…¥

解説でも「これこれで定義される DP で計算すればよいです」「こういう遷移の DP をすればよいです」などと言われるだけで、どう考えてどう思いつくのかを身につけるのが大変だったような記憶があります。最近の人々がどう思っているのかはあまりわかりませんが、えびちゃんが始めた頃（たぶん 7 年くらい前？）はそういう印象でした。

「先頭 $i$ 個見たときの何々の値」とか「先頭 $i$ 個見て何々の値が $j$ のときの何々の値」とか言われても、「なんで先頭 $i$ 個を見ようと思ったの？」という気持ちになっていました。

これに関しては、先頭 $i$ 個を見て考えれば先頭 $i+1$ 個の場合の答えもわかるようなベーシックな問題しか最初は出ないというのがありそうです。 中級以上になってくればそうでない形式の問題も出てきます（後述）。

「自明なケースはなに」で、「そこから考えられる非自明なケースはなにか」あるいは「あるケースを考える上でヒントになる、より自明なケースはなにか」という考え方が基本です。

DP を愚直に眺める

いきなり「先頭 $i$ 個を見たときの何々の値」というのを考えるのではなく、「先頭 $i$ 個を見たときに考えられるケース全体」というのを考えてみることにしましょう。 ナップサック問題の DP を例として使います。

$i$ 番目の商品が重さ $w_i$、価値 $v_i$ のとき、組 $(i, w_i, v_i)$ として表すことにします。$i$ は $0$ から始めることにします。

$\gdef\dp{\operatorname{dp}}$ $\dp[i][j] \triangleq$ (先頭 $i$ 個の商品からいくつか選び、重さをちょうど $j$ にする商品の選び方全体からなる集合)

としてみます。 「先頭 $i$ 個」で選べるのは、$0$ 番目, $1$ 番目, ..., $i-1$ 番目であることに注意しましょう。$i$ 番目は選べません。

まず、$\dp[0][0]$ を考えます。先頭 $0$ 個の商品からいくつか選んで重さをちょうど $0$ にする選び方は、$\emptyset$（すなわち、なにも選ばない）のみなので、$\dp[0][0] = \{\emptyset\}$ とわかります。

また、$\dp[0][1]$ についても考えてみます。先頭 $0$ 個の商品からいくつか選んで重さをちょうど $1$ にする選び方は存在しないので、$\dp[0][1] = \{\} = \emptyset$ とわかります。 同様に、$\dp[0][j] = \emptyset$ ($j>0$) が言えます。

続いて、$\dp[i][j]$ ($i>0$) について考えます。

先頭 $i$ 個のみの商品からいくつか選んで重さをちょうど $j$ にする方法は、

• $i$ 個目の商品（$i-1$ 番）は選ばず、先頭 $i-1$ 個のみの商品からいくつか選んで重さをちょうど $j$ にする
• $i$ 個目の商品を選び（すなわち重さ $w_{i-1}$ が増える）、先頭 $i-1$ 個の商品からいくつか選んで重さ $j-w_{i-1}$ にする選び方と合わせる
  • この選び方は、$j-w_{i-1}\ge 0$ の場合のみ可能
  • あるいは、$j'< 0$ のとき $\dp[i][j']=\emptyset$ と見てもよい

のいずれかとなります。$i$ 個目の商品の有無が異なるので、上記の二つに重複はありません。（漏れがないことはどう示す？ 漏れている選び方の存在を仮定して背理法？）

さて、前者は $\dp[i-1][j]$ と表せます。 後者は、$$\{S\cup \{(i-1, w_{i-1}, v_{i-1})\}\mid S\in\dp[i-1][j-w_{i-1}]\}$$ と表せます。式がごちゃごちゃしてしまっていますが、$\dp[i-1][j-w_{i-1}]$ にある選び方各々について、商品 $i-1$ も追加した選び方を作っているというだけです。

ということで、$\dp[i][j]$ が $\dp[i-1][j']$ ($j'< j$) から求められるとわかったので、$i$ の昇順に $\dp[i][j]$ を求めていくことができそうです（$j$ に関しては適当な順番でよさそうです。並列化することも可能そうですね）。 このときに「$\dp[i][j]$ が $\dp[i'][j']$ ($i'< i$ or $j' < j$) ではうまく表せない」となった場合は、$\dp[i][j][k]$ のように変数を増やしたり、“先頭 $i$ 個” ではない DP を考えたりする必要がありそうです。

具体的な数値での例

適当な例を挙げて考えてみましょう。 商品全体の集合として、たとえば $\{(0, 2, 5), (1, 5, 4), (2, 3, 3), (3, 1, 6)\}$ を考えます。重さが $5$ 以下になるものすべてを、前述の DP に従って求めてみます。

$$ \begin{aligned} \dp[0][0] &= \{\emptyset\}, \\ \dp[0][1] &= \emptyset, \\ \dp[0][2] &= \emptyset, \\ \dp[0][3] &= \emptyset, \\ \dp[0][4] &= \emptyset, \\ \dp[0][5] &= \emptyset, \\ \dp[1][0] &= \dp[0][0] \cup \{S\cup\{(0, 2, 5)\}\mid S\in\dp[0][-2]\} = \{\emptyset\}, \\ \dp[1][1] &= \dp[0][1] \cup \{S\cup\{(0, 2, 5)\}\mid S\in\dp[0][-1]\} = \emptyset, \\ \dp[1][2] &= \dp[0][2] \cup \{S\cup\{(0, 2, 5)\}\mid S\in\dp[0][0]\} \\ &= \emptyset \cup \{\emptyset\cup\{(0, 2, 5)\}\} = \{\{(0, 2, 5)\}\}, \\ \dp[1][3] &= \dp[0][3] \cup \{S\cup\{(0, 2, 5)\}\mid S\in\dp[0][1]\} = \emptyset, \\ \dp[1][4] &= \dp[0][4] \cup \{S\cup\{(0, 2, 5)\}\mid S\in\dp[0][2]\} = \emptyset, \\ \dp[1][5] &= \dp[0][5] \cup \{S\cup\{(0, 2, 5)\}\mid S\in\dp[0][3]\} = \emptyset, \\ \dp[2][0] &= \dp[1][0] \cup \{S\cup\{(1, 5, 4)\}\mid S\in\dp[1][-5]\} = \{\emptyset\}, \\ \dp[2][1] &= \dp[1][1] \cup \{S\cup\{(1, 5, 4)\}\mid S\in\dp[1][-4]\} = \emptyset, \\ \dp[2][2] &= \dp[1][2] \cup \{S\cup\{(1, 5, 4)\}\mid S\in\dp[1][-3]\} = \{\{(0, 2, 5)\}\}, \\ \dp[2][3] &= \dp[1][3] \cup \{S\cup\{(1, 5, 4)\}\mid S\in\dp[1][-2]\} = \emptyset, \\ \dp[2][4] &= \dp[1][4] \cup \{S\cup\{(1, 5, 4)\}\mid S\in\dp[1][-1]\} = \emptyset, \\ \dp[2][5] &= \dp[1][5] \cup \{S\cup\{(1, 5, 4)\}\mid S\in\dp[1][0]\} \\ &= \emptyset \cup \{\emptyset\cup\{(1, 5, 4)\}\} = \{\{(1, 5, 4)\}\}, \\ \dp[3][0] &= \dp[2][0] \cup \{S\cup\{(2, 3, 3)\}\mid S\in\dp[2][-3]\} = \{\emptyset\}, \\ \dp[3][1] &= \dp[2][1] \cup \{S\cup\{(2, 3, 3)\}\mid S\in\dp[2][-2]\} = \emptyset, \\ \dp[3][2] &= \dp[2][2] \cup \{S\cup\{(2, 3, 3)\}\mid S\in\dp[2][-1]\} = \{\{(0, 2, 5)\}\}, \\ \dp[3][3] &= \dp[2][3] \cup \{S\cup\{(2, 3, 3)\}\mid S\in\dp[2][0]\}, \\ &= \emptyset \cup \{\emptyset\cup\{(2, 3, 3)\}\} = \{\{(2, 3, 3)\}\} \\ \dp[3][4] &= \dp[2][4] \cup \{S\cup\{(2, 3, 3)\}\mid S\in\dp[2][1]\} = \emptyset, \\ \dp[3][5] &= \dp[2][5] \cup \{S\cup\{(2, 3, 3)\}\mid S\in\dp[2][2]\} \\ &= \{\{(1, 5, 4)\}\} \cup \{\{(0, 2, 5)\}\cup\{(2, 3, 3)\}\} \\ &= \{\{(1, 5, 4)\}, \{(0, 2, 5), (2, 3, 3)\}\}, \\ \dp[4][0] &= \dp[3][0] \cup \{S\cup\{(3, 1, 6)\}\mid S\in\dp[3][-1]\} = \{\emptyset\}, \\ \dp[4][1] &= \dp[3][1] \cup \{S\cup\{(3, 1, 6)\}\mid S\in\dp[3][0]\} \\ &= \emptyset \cup \{\emptyset\cup\{(3, 1, 6)\}\} = \{\{(3, 1, 6)\}\}, \\ \dp[4][2] &= \dp[3][2] \cup \{S\cup\{(3, 1, 6)\}\mid S\in\dp[3][1]\} = \{\{(0, 2, 5)\}\}, \\ \dp[4][3] &= \dp[3][3] \cup \{S\cup\{(3, 1, 6)\}\mid S\in\dp[3][2]\} \\ &= \{\{(2, 3, 3)\}\} \cup \{\{(0, 2, 5)\}\cup\{(3, 1, 6)\}\} \\ &= \{\{(2, 3, 3)\}, \{(0, 2, 5), (3, 1, 6)\}\}, \\ \dp[4][4] &= \dp[3][4] \cup \{S\cup\{(3, 1, 6)\}\mid S\in\dp[3][3]\} \\ &= \emptyset \cup \{\{(2, 3, 3)\}\cup\{(3, 1, 6)\}\} \\ &= \{\{(2, 3, 3), (3, 1, 6)\}\}, \\ \dp[4][5] &= \dp[3][5] \cup \{S\cup\{(3, 1, 6)\}\mid S\in\dp[3][4]\} \\ &= \{\{(1, 5, 4)\}, \{(0, 2, 5), (2, 3, 3)\}\}. \end{aligned} $$

以上より、（商品全体を考えて）重さがちょうど $j$ ($j\le 5$) になるような選び方は、

• $j = 0$ の場合、$\dp[4][0] = \{\emptyset\}$
• $j = 1$ の場合、$\dp[4][1] = \{\{(3, 1, 6)\}\}$
• $j = 2$ の場合、$\dp[4][2] = \{\{(0, 2, 5)\}\}$
• $j = 3$ の場合、$\dp[4][3] = \{\{(2, 3, 3)\}, \{(0, 2, 5), (3, 1, 6)\}\}$
• $j = 4$ の場合、$\dp[4][4] = \{\{(2, 3, 3), (3, 1, 6)\}\}$
• $j = 5$ の場合、$\dp[4][5] = \{\{(1, 5, 4)\}, \{(0, 2, 5), (2, 3, 3)\}\}$

とわかります。

愚直な DP から無駄を減らす

上記の DP では、結局は選び方を陽に計算しているため、最悪の場合は指数個の値を持つ必要が出てきます。 たとえば、重さ $100$ 以下の選び方を列挙しようとして各商品の重さが全部 $1$ だったら $2^{100}$ 個の選び方を持つ必要がありますね。

さて、典型的な例として、先頭 $i$ 個の商品を使って重さをちょうど $j$ にするときの価値の最大値を考えます。 これは、先ほど考えた $\dp[i][j]$ を用いて $\gdef\placeholder{\bullet}$ $$ \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \dp[i][j]\right\} $$ のように書けます*1。

また、$i$ 個目の商品を使う使わないの分岐を書くと、 $$ \max\,\left(\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \dp[i-1][j]\right\} \cup \left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \{S'\cup \{(i-1, w_{i-1}, v_{i-1})\}\mid S'\in\dp[i-1][j-w_{i-1}]\}\right\}\right) $$ となります（長い...）。$\max A\cup B = \max\,\{\max A, \max B\}$ なので、各々考えます。

複雑な形をしている後者について考えます（前者はすでに同じ形になっているので大丈夫。$(i, j) \gets (i-1, j)$ で置き換えただけの式ということ）。 $$ \begin{aligned} &\phantom{{}={}} \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \{S'\cup \{(i-1, w_{i-1}, v_{i-1})\}\mid S'\in\dp[i-1][j-w_{i-1}]\}\right\} \\ &= \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S\cup\{(i-1, w_{i-1}, v_{i-1})\}} v \Biggm| S \in \dp[i-1][j-w_{i-1}]\right\} \\ &= \max\,\left\{\left(\sum_{(\placeholder, \placeholder, v)\in S} v\right)+v_{i-1} \Biggm| S \in \dp[i-1][j-w_{i-1}]\right\} \\ &= \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \dp[i-1][j-w_{i-1}]\right\}+v_{i-1} \\ \end{aligned} $$

この $\max$ の部分を見ると、先ほど $\dp[i][j]$ から答えを求めた部分の式と同じ形をしていることがわかります。 よって、改めて $$ \dp'[i][j] \triangleq \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \dp[i][j]\right\} $$ とすると、$i\gt 0$ に対して $$ \dp'[i][j] = \max\, \{\dp'[i-1][j], \dp'[i][j-w_{i-1}]+v_{i-1}\} $$ と書けることがわかります。

ベースケースについても計算しておきましょう。 $$ \begin{aligned} \dp'[0][0] &= \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \{\emptyset\}\right\} \\ &= \sum_{(\placeholder, \placeholder, v)\in \emptyset} v = 0, \\ \dp'[0][j] &= \max\,\left\{\sum_{(\placeholder, \placeholder, v)\in S} v \Biggm| S \in \emptyset\right\} \\ &= \max \emptyset = -\infty, \qquad \text{for }j\gt 0. \end{aligned} $$

よって、価値の最大化をしたいだけであれば、選び方全体を保持し続けることなく、各 $\dp'[\placeholder][\placeholder]$ ごとに値一つで済むようになりました。

• $\dp'[0][0] = 0$
• $\dp'[0][j] = -\infty$ for $j \ne 0$
• $\dp'[i][j] = -\infty$ for $j < 0$
• $\dp'[i][j] = \max\,\{\dp'[i-1][j], \dp'[i-1][j-w_{i-1}]+v_{i-1}\}$ for $i\gt 0$

実装の際は、$-\infty$ となるようなエントリはわざわざ持たずにうまくやっても大丈夫です。負の添字をいい感じに扱える言語であれば、それを利用してもよいでしょう。 また、$-\infty$ を $-2^{62}$ のような絶対値の大きい負の数で代用する場合は、最終的な答えが $-\infty$ かどうかの判定の際にバグらせないように注意しましょう（$-2^{62}+v_{i-1} \gt -2^{62}$ などとなり、$-\infty$ に期待している性質と異なったりするため）。

おきもち

いきなり最大値とかを考えて DP しようとせずに、暗に考慮されているケース全体をちゃんと意識してみると、納得しやすい（あるいは、変な考慮漏れをなくせる）のではないかなと思いました。 他にも、最大化ではなく数え上げへの応用（重さがちょうど $j$ になる選び方の通り数は？ 重さがちょうど $j$ になるときの価値の総和は？）もイメージしやすくなりそうです。

また、$\dp'[i][j]$ を求める際に、$\dp[i][j]$ を使った定義式と同じ形の式が出てきたことを意識しましたが、これを意識することが大事です。 「先頭 $i$ 個を見たときの何々の値」が「先頭 $i-1$ 個を見たときの何々の値」から簡単に計算できることが大事なので、そういうようにできる DP の定義を考えたり、そういう値と見做せるような式変形をすることが重要です。

先頭 $i$ 個を見てみるのはそれが一番ベーシックだからです。とりあえずその方針でうまくいかないか考えてみて、だめそうなら別のやり方を検討するとかでよいと思います。 もちろん、それ以外にも典型パターンのようなものはあって、

• 木構造の葉ノードが自明なケースなので、そこから根に向かって求める（木 DP）
• å¹… 1 の区間が自明なケースなので、そこから大きな区間の場合を求める（区間 DP）
• ゴールの状態が自明なケースなので、そこからスタートに向かって求める（期待値、ゲームなど）
• 空集合が自明なケースなので、そこから全体集合に向かって求める（bit DP）
• DAG における入次数 0 のノードが自明なケースなので、そこから各ノードでの値を求める（名前ある？）

などです。「DP と言えば先頭 $i$ 個を見る」ではなくて「DP と言えば自明なケースから」というのが重要です。 自明なケースから始めて、非自明なケースでは同じ形式のより自明なケースに帰着させましょう（自明なケースから順々に求めていくので）。

おわり

今回はナップサック問題の DP を例に挙げましたが、他の典型的な最適化・数え上げの DP であっても、同じように「暗に考えているケースをちゃんと意識する」というのは大事なことだと思います。 慣れてくれば無意識にできるようになると思うので、初めは意識してみるとよいと思います。

人によってしっくりくるイメージは異なるかもしれないですが、なにかしらを得るきっかけになればうれしいです。

*1:$\placeholder$ は、計算に使わない部分を明示しないようにしているだけです。$(i, w_{i}, v_{i})\in S$ と書くと冗長な上、$i$ がかぶって紛らわしくなりそうだったので。