动态规划初步

问题：数字三角形

有一个由非负整数组成的三角形，第一行只有一个数字，出了最下面一行之外的每一个数字的左下方和右下方都有一个数字。

如果从第一行开始，每次可以向左下或右下走一格，怎样的走法能使路径节点和最大。

如果我们把每个格子按照行列编号，然后定义 d(i, j) 为从格子 (i, j) 出发时能得到的最大和，于是原问题即求解 d(1, 1)，可以得到状态转移方程：

• $d(i, j) = a(i, j) + max(d(i+1, j), d(i+1, j+1))$

最优子结构（optimal substructure）：全局最优解包含局部最优解，如果局部不是最优的，那么全局肯定不是最优的。

除了动态规划之外，这个问题还可以使用记忆化 (memoization) 的思想。

DAG 上的动态规划

最长路径问题

嵌套矩形：有 n 个长宽分别为 $(a_i, b_i)$ 的矩形，如果对于两个矩形 X(a, b), Y(c, d)，如果 a<c, b<d 或者 a<d, b<c，那么我们称 X 可以被 Y 嵌套。

给定任意多的矩形，求最长的嵌套序列，使得序列中的每个矩形都能嵌套在后一个中。

这个问题中的“嵌套”就是一个典型的二元关系，可以 DAG 来建模。

在这样一个嵌套关系的 DAG 中，如果设 d(i) 表示从节点 i 出发的最长路长度，边的集合设为 E，那么可以得到有状态转移方程：

• $d(i) = max{d(j) + 1 | (i, j) \in E}$

假设 E 存储在邻接矩阵 G 中，如果我们得到了 G，那么可以用记忆化搜索解决 d 的值：

1
2
3
4
5
6
7

int dp(int i)
{
  int& ans = d[i];
  if (ans > 0) return ans;
  for (int j = i; j <= n; j++) if (G[i][j]) ans >?= dp(j) + 1;
  return ans;
}

固定终点的最长最短路径

硬币问题：有 n 中硬币，面值分别为 $V_1, V_2, \cdots, V_n$，每种都有无限多。给定非负整数 S，可以选用多少个硬币使得面值只和为 S。

输出满足条件的策略中，硬币数量的最大值和最小值。

这个问题同样可以用 DAG 来建模，把每点看作“还需要凑足的面值”，对于还需要凑足 i 的面值设为 $r(i)$，则初始状态为 $r(S)$，目标状态为 $r(0)$。

注意到最大与最小是类似的，我们以最大值为例，伪代码如下：

1
2
3
4
5
6
7
8

int dp(int S)
{
  int& ans = d[S];
  if (ans != -1) return ans;
  ans = -1 << 30;
  for (int i = 1; i <= n; i++) if (S >= V[i]) ans >?= dp(S-V[i])+1;
  return ans;
}

• 注意，用 ans != -1 而不是 ans >= 0，可以区分“无法到达”与“还没算过”这两种情况；

对于需要同时计算最大值的最小值的情况，使用递推而不是迭代更合适：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

min[0] = max[0] = 0;
for (int i = 1; i <= S; i++) 
{
  min[i] = INF; max[i] = -INF;
}
for (int i = 0; i <= S; i++)
	for (int j = 1; j <= n; j++)
    if (i >= V[j])
    {
      min[i] <?= min[i - V[j]] + 1;
      max[i] >?= max[i - V[j]] + 1;
    }
printf("%d %d\n", min[S], max[S]);

调试方式

对于上面的两个题目，可以用下面的方法打印字典序路径：

1
2
3
4
5
6
7
8
9

void print_ans(int i)
{
  printf("%d ", i);
  for (int j = 1; j <= n; j++) if (G[i][j] && d[i] == d[j]+1)
  {
    print_ans(j);
    break;
  }
}

因为 d 的含义是“以 i 为起点的最长路径”，所以上面的方法打印字典序是可行的。另一打印字典序的方式就是在计算的过程中把路径记录下来。

区分“无法到达”与“还没算过”可以单独建立一个 vis 数组。

0-1 背包问题

DAG 的状态

物品无限背包问题：有 n 中物品，每种均有无穷多个。第 i 种物品的体积为 $V_i$，重量为 $W_i$。选一些物品装到一个容器为 C 的背包中，使得在背包内物品的总体积不超过 C 的前提下，重量尽量的大。

跟硬币问题类似，这个问题可以用一个带权的 DAG 建模。

0-1 背包问题：有 n 种物品，每种只有一个。第 i 种物品的体积为 $V_i$，重量为 $W_i$。选一些物品装到一个容量为 C 的背包中，使得背包在物品的总体积不超过 C 的前提下尽量最大。

我们发现套用上面的模型已经不适用了。我们可以参考回溯法中，“阶段”的概念，把 n 种物品的选与不选的两种状态理解为一颗决策树的两个扩展过程。

于是如果我们可以用 d(i, j) 表示当前在第 i 层（即已经做了 i 次决策），剩余容量为 j 时接下来的重量和，那么可以得到状态转移方程：

• $d(i, j) = max{d(i+1, j), d(i+1, j - V_i) + W_i}$
• PS：上述公式即，每次决策的状态由下一次决策是否决定两种状态的最大值确定。

规划方向

对于 0-1 背包问题，我们容易得出一个对称的解法：

• $f(i, j) = max{f(i-1, j), f(i - 1, j -V_i) + W_i}$
• PS：跟上面的状态转移方程是完全对称的，决策树扩展方向恰好相反。

这个扩展方向的好处是：我们不需要多余的内存把 V 和 W 保存下来：

1
2
3
4
5
6
7

for (int i = 0; i <= n; i++) {
  scanf("%d%d", &V, &W);
  for (int j = 0; j <= C; j++) {
    f[i][j] = (i == 1 ? 0 : f[i-1][j]);
    if (j >= V) f[i][j] >?= f[i-1][j-V] + W;
  }
}

滚动数组

为了降低空间复杂度，我们甚至可以把 f 降成一维的：

1
2
3
4
5
6

memset(f, 0, sizeof(f));
for (int i = 0; i <= n; i++) {
  scanf("%d%d", &V, &W);
  for (int j = C; j >= 0; j--)
    if (j >= V) f[j] >?= f[j-V] + W;
}

递归结构中的动态规划

最优矩阵链乘：给出 n 个矩阵组成的序列，第 i 个矩阵 $A_i$ 的是 $p_{i-1} \times p_i$ 的，设计一种方法把它们依次乘起来，使得运算量最小。

因为矩阵的乘法满足结合律而不满足交换律。不同优先级的乘法计算方式，则会有不同的计算量。

我们考虑一个子问题 $f(i, j) \Rightarrow \text{运算次数}(\prod_{k = i}^{j} A_k)$ ，状态转移方程：

• $f(i, j) = max{f(i, k) + f(k, j) + p_{i-1}p_kp_j}$

• 运算的边界为 $f(i, i) = 0$

这个问题的特殊性在于：不同于 DAG 上的动态规划，这里的动态规划在计算时无论是按照 i 还是 j 的递增或递减的顺序均不正确。更合理的方法是按照 j-i 递增的方式递推。

最优三角形划分：对于一个 n 个顶点的凸多边形，有很多种方法可以对他进行三角刨分，即用 n-3 条互不相交的对角线把凸多边形分成 n-2 个三角形。

为每个三角形规定一个权函数 w(i, j, k)，求让所有三角形权和最大的分割方案。

相对于“最优矩阵链乘积”，这个问题的特殊性在于：我们没有一个清晰的决策过程。

我们可以定义一个状态 $f(i, j)$ 表示从顶点 i 到顶点 j 所构成的子多边形的最大三角形刨分劝和，即可得到一个清晰的决策过程。

这样我们就把决策起点设置为任意的 f(1, 1)，可以证明从任何一个顶点作为起点开始，不影响决策结果。可以得到状态转移方程：

• $f(i, j) = max{f(i, k) + f(k, j) + w(i,j,k)}$

树的最大独立集：对于一颗 n 个节点的无根树（即无环无向图），选出尽量多的节点，使得任意两个节点均不相邻，则我们称这些节点构成的集合称为“最大独立集”。

给定 n-1 条无向边，输出一个最大独立集。

同样的我们需要一个清晰的决策过程，我们把任何一个节点设置为根节点，即可自顶向下进行递归。

对于每个节点 i 只有两种决策：选或不选。这两种分别对于不同的决策结果，可以得到状态转移方程：

• $\displaystyle d(i) = max{1 + \sum_{j \in grand_son(i)} d(j), \sum_{j \in son(i)} d(j)}$

集合上的动态规划

最优配对问题：空间中有 n 个点 $P_0, \cdots, P_{n-1}$，n 为偶数。可以有多种方式将这 n 个点配对成 n/2 个数对，求一种配对方式是的所有点对中两点距离之和最小的那种配对方式。

多阶段决策：

• 先确定 $P_0$ 要和谁配对，以此类推最后确定 $P_{n-1}$ 要和谁配对。

状态：

• $d(i, S) \Rightarrow$ 前 i 个点组成的集合 S，元素两两匹配的最小值；
• 注意到 i 实际上就是 S 这个集合中的最大值，所以我们可以用 d(S) 来更简洁地表示这个状态

状态转移方程：

• $d(i, S) = min{|P_iP_j| + d(i - 1, S - {i} - {j}) | j \in S}$
• 优化：$d(S) = min{|P_iP_j| + d(S - {i} - {j})| j \in S, i = max{S}}$

针对于这个题目，我们还需要一个表示集合的方法，可以用下表标{0, 1, 2, ..., n-1} 唯一表示一个元素，然后有二进制编码表示一个子集。

代码实现：

1
2
3
4
5
6
7
8

for (int S = 0; S < (1<<n); S++)
{
  int i, j;
  d[S] = INF;
	for (int i = 0; i < n; i++) if (S && (1 << i)) break;
  for (j = i+1; j<n; j++) if (S & (1<<j))
    d[S] <?= dist(i, j) + d[S^(1 << i)^(1<<j)];
}

总结

我理解动态规划的本质是对回溯的“空间换时间”优化，当一个问题的决策路径过长，但是决策空间在一定范围内时，我们可以通过计算这个决策空间中的所有情况，来迭代式地计算出原问题的解。

动态规划一般可以拆分成以下的几步：

• 决策：找出一个多阶段决策方式；
• 状态：确定一种能够唯一描述一个决策中间状态的方法。状态表示有以下的两个核心考虑点：
  • 状态的参数、维度：可以用穷举的变量参数做参数，二维的时间复杂度 $$O(n^2)$$。也可以用一个集合的子集做参数，单个集合的时间复杂度是 $$O(2^n)$$；
  • 状态的对应的值：值是为状态转移方程服务的，可以是一个数字、结构、bool 值等；
• 转移：列举出状态转移方程。

优化方式：

• 动态规划通常存在两种规划方向，有的方向可以节省空间；
• 滑动数组一般可以把空间复杂度从 $$O(n^2)$$ 降低到 $$O(n)$$