动态规划

本文内容参考《算法导论》，OI Wiki。

基础知识

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。

适合应用动态规划方法求解的最优化问题应该具备两个要素：最优子结构和重叠子问题。

• 最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
• 重叠子问题：如果问题的递归算法会反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。

子问题图

子问题图是一个有向图，每个顶点唯一的对应一个子问题。若求子问题 \(x\) 的最优解时需要直接用到子问题 \(y\) 的最优解，那么在子问题图中就会有一条从子问题 \(x\) 的顶点到子问题 \(y\) 的顶点的有向边。

自顶向下动态规划处理子问题图中顶点的顺序为拓扑序，自底向上动态规划处理子问题图中顶点的顺序为逆拓扑序。

通常情况下，动态规划算法的运行时间与子问题图中顶点和边的数量呈线性关系。

选择自顶向下，还是自底向上

通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会更快，因为没有递归调用的开销，而且对于某些问题，可以利用表的访问模式降低时空开销。如果子问题空间中的某些子问题完全不必求解，自顶向下动态规划算法会更快，因为它只会求解那些必要的子问题。

背包 DP

题目：有 \(n\) 种物品和一个容量为 \(W\) 的背包，每种物品有数量 \(k_{i}\)、重量 \(w_{i}\) 和价值 \(v_{i}\) 三种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

0-1 背包

每种物品只能取一次，即 \(k_{i}=1\) 对任意 \(i\) 都成立。

转移方程：

$$ dp[i][j]=\max{(dp[i-1][j],dp[i-1][j-w[i]]+v[i])} $$

空间优化（倒序枚举）：

$$ dp[j]=\max{(dp[j],dp[j-w[i]]+v[i])} $$

完全背包

每种物品可以取无限次，即 \(k_{i}=\infty\) 对任意 \(i\) 都成立。

转移方程：

$$ dp[i][j]=\max_{k=0}^{\infty}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

方程优化：

$$ dp[i][j]=\max{(dp[i-1][j],dp[i][j-w[i]]+v[i])} $$

空间优化（正序枚举）：

$$ dp[j]=\max(dp[j],dp[j-w[i]]+v[i]) $$

多重背包

每种物品可以取 \(k_{i}\) 次，即 \(k_{i}\in\mathbb{N}\) 对任意 \(i\) 都成立。

转移方程：

$$ dp[i][j]=\max_{k=0}^{k[i]}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

二进制分组优化：将每种物品的 \(k_{i}\) 拆分为多个组，每组的数量为 \(2^{0},2^{1},\dots,2^{\lfloor{\log{k_{i}+1}}\rfloor -1}\)，如果 \(k_{i}+1\) 不是二的幂，就将多余的数量作为一组，最后将 \(k_{i}\) 拆出来的每组都看作数量为 \(1\) 的新物品，从而转化为 0-1 背包。可以证明，如果选择 \(x\) 次第 \(i\) 种物品，其中 \(x\in[0,k_{i}]\)，则该选择方式总是可以由分组后的新物品的某个组合表示。

例题

• 线性 DP：1143. 最长公共子序列，300. 最长递增子序列，72. 编辑距离。
• 背包 DP：416. 分割等和子集，322. 零钱兑换，2902. 和带限制的子多重集合的数目。
• 区间 DP：516. 最长回文子序列，1000. 合并石头的最低成本。
• 树形 DP：2646. 最小化旅行的价格总和，834. 树中距离之和，2867. 统计树中的合法路径数目。
• 状压 DP：526. 优美的排列，Mondriaan’s Dream。
• 数位 DP：233. 数字 1 的个数，1012. 至少有 1 位重复的数字。
• 概率 DP：D. Bag of mice，E - Roulettes。