跟 Nachia DP 博客学DP-7&8: 分发型 接收型 DP

跟 Nachia DP 博客学DP-7&8 分发型 接收型 DP

Nachia 原文： DP 的俗称 | Mathenachia --- DP の俗称 | Mathenachia

背包问题通常可以用上列两种情况来实现，所以很多人认为：任何 DP 问题都能在这两类 DP 处理方式中轻松转换.

下面我们仅考虑像 $dp[i]$ 这样只有一个下标的 DP，对于多个下标比如 $dp[i][j]$ 这样的，可以通过编码为 $dp[i \times n + j]$ 等方式来规约，如果我们把编码后的一对表示为 $\langle i, j\rangle$ 这样的形式，比如 $dp[\langle i, j\rangle]$

为了计算 $dp[i]$ 的值而需要 $dp[j]$ 的值时，考虑一条边指向 $j \to i$ 图，需要注意的是，根据 DP 的定义，$j$ 和 $i$ 未必是大小关系链接

如果设顶点 $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 需要反复处理 $dp[i] \gets g(dp[i], dp[j])$ 这样的更新操作，因此不太擅长处理这样的情况

接收型 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_{+}(\langle i, j\rangle)= \set{ \langle i + 1, j \rangle, \langle i + 1, j + w_i \rangle }.$

另一方面，逆向好像也很好求：

• $\delta_{-}(\langle i, j\rangle)= \set{ \langle i - 1, j \rangle, \langle i - 1, j - w_{i-1} \rangle }.$

因此，无论选择上述哪种实现，其实都没有问题.

dp[0][0] = 0
其他 dp = -∞

for i = 0 to n-1:
    for j = 0 to W:
        if dp[i][j] == -∞: continue
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + w[i+1] <= W:
            dp[i+1][j + w[i+1]] = max(dp[i+1][j + w[i+1]], dp[i][j] + v[i+1])

ans = max(dp[n][j]) for j = 0 to W

dp[0][0] = 0
其他 dp = -∞

for i = 1 to n:
    for j = 0 to W:
        dp[i][j] = dp[i-1][j]
        if j >= w[i]:
            dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i])

ans = max(dp[n][j]) for j = 0 to W

埃式筛法

其实可以看作是 DP，$dp[i]$ 的定义是表示 “$i$ 是素数” 的布尔值.

当 $i$ 是合数的时候无需筛选，因此可以说 $\delta_{+}(i) = \varnothing$. 当 $i$ 是素数的时候，则为 $\delta_{+}(i) = \set{ i \cdot j : j \gt 1 }$ . 这些都可以轻松计算，可以通过 $dp[i'] \gets dp[i'] \land dp[i], (i' \in \delta_{+}(i))$ 来更新.

另一方面的话，能不能轻松的计算 $\delta_{-}(i)$ 呢？如果可以的话，那么根本就不需要筛法之类的东西来质因数分解了吧哈哈

因此这东西与 分发型 DP 相性好，但和 接收型 DP 相性差，其余筛法也是如此.

dp[2..n] = true      // 假设全是素数
dp[0] = dp[1] = false
for i = 2 to n:
    if dp[i] == true:                     // i 是素数
        for j = 2 to n/i:
            dp[i * j] = false             // 标记倍数为合数

涉及操作的问题，比如期望次数、博弈游戏等

从给定状态（也可称局面）到达最终形态所需的操作次数期望，以及判定两人游戏的胜负等问题十分常见. 在这些问题设定中，显然的案例是最终形态（例如可以分别得出 “期望值是 0” “该局面判输” 等结论）. 因此，边会从操作后的状态指向操作前的状态. 有些人会因此感觉违和，但请控制你的 “直觉”！

这样的问题设定中， $\delta_{-}(s)$ 指的是 “从局面 $s$ 进行一次操作后可以得到的局面（们）”， $\delta_{+}(s)$ 指的是 “通过一次操作能够变成局面 $s$ 的局面（们）”. 通常题目考虑前者会更自然，但设定不同，两者可能都被考虑.

从最终状态重复 $\delta_{+}$ 到达初始状态并非显而易见，因此从常常会计算出从初始状态无法到达的无用局面；另外，如果从初始状态重复 $\delta_{-}$，则可以只聚焦于从初始状态可达的局面，这看起来是很好的

$\delta_{-}$ 与记忆化递归配合起来效果会更好. 一般来说，当计算顺序不明确的时候，记忆化递归往往更合适. 这相当与对 DP 图进行 DFS. 这样说来，好像用 BFS 也可以，但感觉这样的实现不多

在类似双六棋这样简单的设定中，DP 的图会变成路径图，因此从终点格子开始按顺序循环的实现方式往往更简单。不仅限于游戏类，能否用循环轻松编写似乎取决于图的形状呢。

最短路问题

Dijkstra 算法可以看作是 DP. 虽然 DP 的更新顺序是动态的，但这样应该没什么问题.

由于图的边直接成为 $\delta_{\pm }$，因此取决于图的表示方式，但如果持有普通的邻接列表，计算 $\delta_{+}$ 似乎更为自然. 当从堆中取出 $i$ 的时候，意味着针对 $j \in \delta_{-}(i)$ 计算了 $dp[j]$

总结

常说 “DP 就是 DAG”，但实际上关注边计算部分的讨论不多

能从多种角度看待该问题，思路也会更加开阔

拓展阅读与例题

拓展阅读

動的計画法（DP）と重みつきグラフ、あるいは添字と値の入れ替えについて #競技プログラミング - Qiita

DPはDAG上の最短経路ではない - うさぎ小屋

DPの話 - aizuzia

关于分发型 DP 与接收型 DP 的特征化 - 虾酱的日记 --- 配る DP・もらう DP の特徴づけに関して - えびちゃんの日記