配る DP・もらう DP の特徴づけに関して

典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP を集める DP と呼ぶ派閥もあった気がしますが、ここでは名称についての議論はしません。

å°Žå…¥

初心者向けの解説の多くでは、ナップサック問題の DP などを例に出して、

for i in 0..n {
    for j in 0..=cap {
        dp[i + 1][j] = dp[i + 1][j].max(dp[i][j]);
    }
    for j in 0..=cap - w[i] {
        dp[i + 1][j + w[i]] = dp[i + 1][j + w[i]].max(dp[i][j] + v[i]);
    }
}

で更新するのが配る DP で、

for i in 1..=n {
    for i in 0..=cap {
        dp[i][j] = dp[i][j].max(dp[i - 1][j]);
    }
    for j in w[i - 1]..=cap {
        dp[i][j] = dp[i][j].max(dp[i - 1][j - w[i - 1]] + v[i - 1]);
    }
}

で更新するのがもらう DP ですーと説明されることが多そうな気がします。

よく「dp[i][j] が右辺にあるか左辺だけにあるか」とかで説明されがちな気がしますが、あまり本質的でない気がします。 ループの範囲を変えるだけで見かけ上は変わってしまうためです。

for i in 1..=n {
    for j in 0..=cap {
        dp[i][j] = dp[i][j].max(dp[i - 1][j]);
    }
    for j in 0..=cap - w[i - 1] {
        dp[i][j + w[i - 1]] = dp[i][j + w[i - 1]].max(dp[i - 1][j] + v[i - 1]);
    }
}

そもそも、ナップサック問題は単純な計算でできてしまうため、配る・もらうをうまく呼び分けるのが難しいというか、これを例に出して区別しようとするメリットが薄い気がします。 また、この例のせいで「配る・もらうはあくまで実装方針の違いだけで、どんな DP でも双方を行き来することが容易」のような感覚になりやすい気がします。

主張

$\gdef\DP{\operatorname{dp}}$

以下では、$\DP[i]$ のように添字が一つの DP のみを考えます。$\DP[i][j]$ のようなものについては、適宜 $\DP[i\times n+j]$ のように encode するなどして帰着させればよいです。必要に応じて、encode した整数を $\angled{i, j}$ のように表すことにします（$\DP[\angled{i, j}]$ など）。

$\DP[i]$ の計算をするために $\DP[j]$ の値を必要とするとき、$j\to i$ に辺を持つグラフを考えます*1。 DP の定義によっては、必ずしも（整数の意味での大小関係として）$j\lt i$ とは限らないことに注意しておきます。

(* note: 全体を書いてから Introduction to Algorithms を読み直したところ、上記の状況で $i \to j$ の辺を張るグラフが subproblem graph として記載されていました。書き直すのが大変なのでこのままにしておきます。*)

グラフに関して

グラフを知らない人へ： たとえば $y = x^2+1$ のようなグラフの話ではないです。いくつかの丸（頂点と呼ばれます）たちを、いくつかの矢印（辺と呼ばれます）で結んだり結ばなかったりして得られる絵のことだと思ってもらえばよいと思います。詳しく知りたい場合は「グラフ理論」とかでググるとよろしいです。

競プロ初心者で、「グラフ」に苦手意識がある人・グラフ関連のアルゴリズムがわからずに苦しんでいる人へ： ここではそういう話は出てこないので落ちついてください。あくまで頂点の集合と辺の集合を考えたいだけです。

頂点 $i$ に入ってくる辺を持つ頂点の集合を $\delta_-(i)$ と書くことにします。また、頂点 $j$ から出ていく辺を持つ頂点の集合を $\delta_+(j)$ と書くことにします。 つまり、$\DP[i]$ を計算するためには、各 $j\in\delta_-(i)$ に対して $\DP[j]$ が計算されている必要があるということです。 逆に、$\DP[j]$ を計算し終えたら、各 $i\in\delta_+(j)$ に対して $\DP[i]$ の計算に使う情報の一つがわかったことになります。

さて、グラフ自体は（実装によらず）DP の定義と入力ケースから定まりますが、そのグラフを得ることが簡単とは限りません。 すなわち、実装する上では次のことが大事になってきます。

• $i$ から $\delta_-(i)$ を計算することは容易か？
• $j$ から $\delta_+(j)$ を計算することは容易か？

ということです。前者が容易なときにそれを利用して求めるのが「もらう DP」、後者が容易なときにそれを利用して求めるのが「配る DP」という特徴づけができると思っています。 後者に基づくときでも、適切な順序で計算するなどして、$\DP[i]$ の計算時には各 $j\in\delta_-(i)$ の計算は終えていることを担保する必要があります（後述）。

もらう DP は $\DP[i] = f(\delta_-(i)) = f(j_1, j_2, \dots)$ のように、等式の形での記述と相性がよさそうです（$\DP[i]$ の計算の際はそれに従えばよい）。 一方、配る DP は $\DP[i] \gets g(\DP[i], \DP[j])$ のような更新を繰り返すため、そうした部分は苦手そうです。

もらう DP は “関数型” っぽくて配る DP は “手続き型” っぽいという見方もできそうです。 手続き型よりも関数型風の方が不変条件や正当性などを考えるときも楽そうなので、アルゴリズムの教科書などではもらう DP っぽい形式のものが多く書かれているような印象があります。気のせいかもしれません。

また、もらう DP では「複数のものからなにかを計算する処理」、配る DP では「複数のものに更新をする処理」が必要になり、$\delta_{\pm}$ の計算だけではなく、それらを実現するデータ構造との相性も重要です。一般に、前者タイプのデータ構造の方が充実している印象があります。

例

ナップサック問題

ナップサック問題の例では、$\DP[i][j]$ を「先頭 $i$ 個の商品のうち、重さが $j$ となる組合せの価値の最大値」とすると $(i, j) \to (i+1, j)$ および $(i, j) \to (i+1, j+w_i)$ の辺が各 $(i, j)$ に張られることになります。 すなわち、下記のように表せます（対象の範囲外になる辺は適宜無視することにします）。 $$ \delta_+(\angled{i, j}) = \{\angled{i+1, j}, \angled{i+1, j+w_i}\}. $$ 一方、逆向きも簡単に求めることができます。 $$ \delta_-(\angled{i, j}) = \{\angled{i-1, j}, \angled{i-1, j-w_{i-1}}\}. $$

よって、どちらに基づいた考えで実装しても大丈夫そうです。

Eratosthenes の篩

これを DP と見做している初心者はあまり多くないのかもしれませんが、DP と見做せます。 $\DP[i]$ の定義は、「$i$ が素数である」を意味する boolean です。

$i$ が合成数のときにふるう必要はないので、$\delta_+(i) = \emptyset$ と言えます。 $i$ が素数のときは、$\delta_+(i) = \{i\cdot j \mid j \gt 1\}$ です。 これらは容易に計算することができます。$\DP[i'] \gets \DP[i'] \wedge \DP[i]$ ($i'\in\delta_+(i)$) で更新するわけですね。

一方、$\delta_-(i)$ を容易に計算することは可能でしょうか。 これが可能であるのなら、そもそも篩なんてものを使わずに高速に素因数分解できてしまうんですよね*2。

よって、これは配る DP とは相性がよいですが、もらう DP とは相性がよくないわけです。 線形篩なども同様です。

回数の期待値・ゲームなど、操作を伴うもの

与えられた状態（盤面と呼んでもよい）から終状態に到達するまでの操作回数の期待値や、二人ゲームの勝敗判定（主に、操作できなくなった人が負け）などの問題は頻出です。 これらの問題設定においては、自明なケースは終状態です（それぞれ「期待値は 0」「その局面は負け状態」などとわかる）。 そのため、操作後の状態から操作前の状態に向かって辺が向かう形になります。 違和感を持つ人もいるようですが、“直感” に振り回されないようにしましょう。

さて、こうした問題設定においては、$\delta_-(s)$ は「盤面 $s$ から操作を一度したときの盤面（たち）」、$\delta_+(s)$ は「操作を一度することで盤面 $s$ にできる盤面（たち）」を指すことになります。 問題設定によってはどちらを考えることも可能でしょうが、操作が問題文で与えられることを考えると前者の方が自然になることが多い気がします。

終状態から $\delta_+$ を繰り返すことで初期状態に辿りつくのは自明ではなかったり、初期状態から到達できない無駄な盤面を計算してしまうことも多いです。 また、初期状態から $\delta_-$ を繰り返せば、初期状態から到達可能な盤面のみに絞ることができてうれしそうです。

$\delta_-$ であればメモ化再帰と相性がよいです。一般に、計算順序が自明でないときはメモ化再帰がよいことが多そうです。DP のグラフを DFS しているのに相当しそうです。 それで言うと BFS でもよさそうな気もしますが、あまりそういう実装をすることは少ないような気がします。

すごろくのような単純な設定では DP のグラフがパスグラフになるため、ゴールマスから順にループする実装の方が単純になることも多いでしょう。 ゲーム系に限らず、ループで簡単に書けるかどうかはグラフの形状によりそうですね。

最短距離

すみません、ここ怪しいです。簡単な例として負辺があるグラフ、トポソ不可能な有向グラフなどを考えるといろいろこわれそうです。ここの節はなかったことにしたいです。

Dijkstra 法も DP と見做せそうです。 DP の更新の順序は動的に決まりますが問題はないでしょう。

グラフの辺がそのまま $\delta_+$・$\delta_-$ になるので、グラフの表現の仕方によりそうですが、普通の隣接リストを持っていれば $\delta_+$ を計算する方が自然になりそうです。 ヒープから $i$ が取り出されれば $j\in\delta_-(i)$ に対して $\DP[j]$ が計算されたことになります（言うほど自明ではないような気がします）。

所感

よく「DP は DAG」などと言われますが、辺の計算の部分に着目しているものはあまり見なかったような気がしました。

See also:

• https://tayama-2.hatenadiary.org/entry/20111210/1323502092
• https://kmyk.github.io/blog/blog/2019/09/19/dp-is-not-shortest-path-of-dag/
• https://qiita.com/hibit/items/ecfae3777cf56ac6281b

いろいろな見方ができるようになると発想の幅も広がりそうです。

おわり

近いうちにまた DP のお話をする予定です。次は典型的な各種 DP に関するお話です。

*1:グラフの頂点集合は $\N$ の部分集合である必要はないので、$\DP[i][j]$ のようなタイプの DP でも $(i, j)\to(i', j')$ のようなグラフを考えてもよかったですね。あんまりここでの本質ではなさそうです。

*2:篩は素数判定だけでなく素因数分解もできるんですよね。