算法-动态规划(十)

概述

本文主要介绍 DAG 上 DP，与其相关的题目有：嵌套矩形、硬币问题。

DAG 上 DP 问题，其本质在于将题目转换为有向无环图 (DAG) 上的最短路径、最长路径、路径计数等问题，从而使用动态规划进行求解。

嵌套矩形

题目描述及示例

有 $n$ 个矩形，每个矩形可以用 $a,b$ 来描述，分别表示长和宽。矩形 $X(a,b)$ 可以嵌套在矩形 $Y(c,d)$ 中当且仅当$a<c,b<d$ 或者 $b<c,a<d$。例如 $(1,5)$ 可以嵌套在 $(6,2)$ 内，但不能嵌套在 $(3,4)$ 中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

Input:
// 第一行包含整数n，表示矩形数量。
10
// 接下来n行，每行包含两个整数，分别表示矩形长和宽。
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
    
Output:
// 输出一个整数，表示最多符合条件的矩形数目。
5

解题思路

• 数据存储

  根据题意，可以看到：矩形嵌套成立条件有些复杂，为简化操作，对于每个矩形而言，我们将小值作为矩形的宽，大值作为矩形的长。此时只需判断两个矩形的宽长是否满足大小，即可判断矩形嵌套是否成立。

  这道题目可以如此理解：每个矩形对应图中一个结点，如果矩形 $A$ 可以嵌套于矩形 $B$ 之内，则矩形 $B$ 所在结点引出一条有向边指向矩形 $A$ 所在结点。“最多符合嵌套条件的矩形数目” 便可理解为图中最长路径的所占结点数量。

  graph[i][j] 用于存储结点间权值信息，如果结点间存在边，则权值为 $1$，否则权值为 $0$。

• 状态表示

  我们可以这样表示状态 $f[i]$：以当前结点 $i$ 作为终点，其路径上所占结点的最多数量。

• 状态转移

  状态表示已然出现，状态转移便是比较简单。对于状态 $f[i]$ 而言，其应当由状态 $f[j]$ (结点 $j$ 需有边指向结点 $i$) 转移得到。

  状态转移方程具体表示如下：

  $$f[i] = max(f[j] + graph[j][i]),(0 \leq j < n)$$

  因边权值设置，我们可如此表示状态。

• 状态初始化

  对于图而言，自然使用记忆化搜索实现。首先需要将所有状态置为未知 (可使用状态值为 $-1$ 表示未知)；搜索过程中，如果不存在指向当前结点 $i$ 的结点，则置 $f[i] = 1$。

硬币问题

题目描述及示例

有 $n$ 种硬币，面值分别为 $V_1, V_2···,V_n$，每种都有无限多。给定非负整数 $S$ ，可以选用多少个硬币，使得面值之和恰好为 $S$？输出硬币数目的最小值和最大值。

Input:
// 第一行包含两个整数n,s。
3 18
// 接下来n行，每行包含一个整数，表示硬币面值。
1
2
5

Output:
// 输出两个整数，分别表示硬币数目的最小值和最大值。
5 18

解题思路

• 数据存储

  该题可以这样理解：整数 $0 \sim S$ 分别表示图中一个顶点，对于整数 $i,j \ (j > i)$ 而言，如果 $j - i$ 对应某种面值的硬币，则整数 $i$ 所在结点引出一条有向边指向整数 $j$ 所在结点。“硬币数目的最小值和最大值” 便可理解为：从整数 $0$ 所在结点到整数 $S$ 所在结点的所有路径中，最长路径的长度和最短路径的长度。

  graph[i][j] 用于存储结点间权值信息，如果结点间存在边，则权值为 $1$，否则权值为 $0$。

• 状态表示

  我们可以这样表示状态 $f[i]$：以当前结点 $i$ 作为终点，其最长路径的长度，$p[i]$：以当前结点 $i$ 作为终点，其最短路径的长度。

• 状态转移

  状态转移与上题类似，我们直接给出状态转移方程：

  $$f[i] = max(f[j] + graph[j][i]),(0 \leq j < n)$$

  $$p[i] = min(p[j] + graph[j][i]),(0 \leq j < n)$$

• 状态初始化

  对于图而言，自然使用记忆化搜索实现。首先需要将所有状态置为未知 (可使用状态值为 $-1$ 表示未知)；搜索过程中，如果当前结点所示整数为 $0$，则置 $f[i] = 0,p[i] = 0$，如果当前结点没有任何结点指向，则置 $f[i] = -INF,p[i] = INF$ ($INF$ 表示无穷大)。