基础动态规划 $Dynamic\ Programming$
主要思想
类似于递推, 将当前状态的属性（最大值 $max$, 最小值 $min$, 解的个数 $nums$）由上一个状态转移而来, 从而继承上一个状态的属性, 具有最优子结构属性, 由此得出状态转移方程.
$\rm dp$ 的状态转移方程可以有两种思考方式：顺推和逆推. 顺推即考虑当前状态能向后推出何状态, 逆推即考虑当前状态由哪些状态转移而来.
状态转移方程的推导方式
以 openjudge4008-糖果 为例.
1. 顺推
1 | f[i + 1][j] = f[i][j]; // 不选当前第 i + 1 件物品 |
值得注意的是, 在顺推中 $f_{i, j}$ 表示未计算 $i, j$ 值的状态, 因此顺推的目标解为 $f_{n + 1, k}$.
2. 逆推
1 | f[i][j] = f[i - 1][j]; // 不选当前第 i 件物品 |
对于两种状态取 $max$ 即可.
同时, 该状态需要具有无后效性的特点, 即当前状态的选择无法影响下一状态的决策.
另外值得注意的是, 我们需要对dp边界的初始值进行特判.
动态规划问题的时间复杂度分析
状态数量 * 转移计算量
背包问题：
给定 $n$ 个物体, 和一个容量是 $v$ 的背包, 每个物体的体积是 $vi$, 权重是 $wi$, 求如何装物品使得总权重最大
在背包问题中, 一般用 $f_{i, j}$ 表示所有从前 $i$ 个物品中选并且总体积不超过 $j$ 的所有选法中 最大 / 最小 的总价值
经典背包问题特点
| 背包问题 | 特点 |
|---|---|
| $0/1$ 背包 | 每件物品最多只能用一次 |
| 完全背包 | 每件物品可以用无限次 |
| 多重背包 | 每件物品可以使用有限次 |
| 分组背包 | 将所有物品分为若干组, 每组物品中最多只能选一个物品 |
另外为了方便叙述, 在以下的讲解中, 各数组含义如下：
1 | int n, m; // n 表示所有物品的个数, m 表示背包容量 |
$0/1$ 背包
尝试考虑暴力：
1 | // for (int j = 0; j <= m; j ++) f[0][j] = 0; |
在 dp 每一层的状态计算中不难发现, 每一层第一维度的值都和上一层的值有关 f[i][j] = f[i - 1][j] , 第二维度的值只可能出现 j 或 j - v[i], 那么可以利用滚动数组对空间进行优化：
1 | for (int i = 1; i <= n; i ++) |
看到这里, 如果您对于为何倒序枚举的问题仍不是很明白, 那么可以尝试使用暴力枚举的方法做一下 $\rm Luogu\ P2347$ - 砝码称重. 通过思考这道题的枚举顺序, 能够加深您对背包枚举顺序的理解.
不难发现, 分别枚举砝码种类, 砝码个数, 在可用的重量上加上当前种类的重量即可.
1 | for (int i = 0; i < 6; i ++) |
在枚举砝码的时候, 如果 $k$ 正向枚举, 会出现刚刚用过的砝码继续在下一层重量循环累积, 而一个砝码在同一个砝码循环是只能用一次的. 而由于 $f[k+w[i]]=1$ 一定是大于 $f[k]$ 的, 因此使用倒序枚举会有效规避掉此问题.
同时我们发现, 当 $k$ 正向枚举时, 会将同一个砝码重复使用若干次. 于是, 完全背包的一维优化由此延伸, 使用正序枚举即可, 让我们接着往下读！
完全背包
完全背包的状态计算：
类比于 $0/1$ 背包将当前情况分为 选 ( $1$ ) 或 不选 ( $0$ ), 在完全背包中可以按照选多少个物品分类
对于各个集合中状态的表示, 设当前物品选了 $k$ 个, 即有状态转移方程：
$$ f_{i, j} = f[i - 1][j - k * v_i] + k * w_i $$
将每个情况取最大值, 即可求出当前情况的价值最大值
暴力
1 | for (int i = 1; i <= n; i ++) |
一维优化：
当对 $f_{i, j}$ 进行枚举时, 进行的过程是这样的：
$$ f[i, j] = max(f[i, j], f[i, j - v_i] + w_i, f[i, j - 2 * v_i] + 2 * w_i, …) $$
在枚举 $f_{i, j}$ 时, 我们已经完成了对 $f_{i, j - v_i}$ 的枚举, 当时进行的过程是这样的：
$$ f[i][j - v_i] = max(f[i][j - v_i], f[i - 1][j - 2 * v_i] + w_i, …) $$
此时我们发现, 计算 $f_{i, j}$ 的过程与计算 f[i][j - v[i]] 的过程非常相似, 规律可以表述为：
max(f[i, j - v[i]] + w[i], f[i, j - 2 * v[i]] + 2 * w[i], ...) = f[i, j - v[i]] + w[i]
那么我们可以将状态转移方程优化为：
1 | for (int i = 1; i <=n; i ++) |
此时的状态转移方程为：f[i][j] = max(f[i][j], f[i][j - v[i] + w[i]])
而在01背包中的状态转移方程为：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] + w[i]])
类比于 $0/1$ 背包的一维优化, 我们可以将完全背包优化为：
1 | for (int i = 1; i <=n; i ++) |
到此为止, 我们已经将完全背包的空间复杂度优化到了 $O(n)$
此时我们会惊奇地发现, 完全背包的一维优化与 $01$ 背包的一维优化极其相似. 关键点在于 $j$ 的枚举顺序, 倒序枚举表示当前情况中不包含当前这一层物品的选择, 也就保证了当前层物品选择的唯一性 ( $0$ / $1$ ). 而在完全背包中, 任何一件物品都有无数件, 因此从前向后转移就包含了前面对于这一层物品的选择, 从而达到最优
多重背包
对于每个物品都有个数限制 $s_i$, 只需枚举物品个数 $k$ 并使 $k$ 满足 $ k \le s_i$ 且 $k * v_i \le j$
朴素 $O(nms)$
1 | for (int i = 1; i <= n; i ++) |
多重背包的二进制拆分优化 $O(w \cdot n \cdot \log s)$：
基本原理：
假设s = 1023, 如按照朴素方式枚举, 则需要枚举 1023 次. 此时我们将 1 ~ 1023 分为十组, 每组分别是：
$2^0, 2^1, 2^2, 2^3, \cdots, 2^9$
即：$1, 2, 4, 8, …, 512$
易证对于 $[1, 1023]$ 区间中的每一个数字, 都可以用以上 $10$ 个数表示
当 $s$ 不为 $2$ 的正整数次方时, 假设 $s = 200$, 此时我们将 $200$ 分为以下几组：
$2^0, 2^1, 2^2, 2^3, 2^4, 2^5, 2^6, 73$
此时即可以用以上几组数据将 [1, 200] 区间中所有的数字表示出来
将 $s$ 推广为一般数字：
$2^0, 2^1, 2^2,…, 2^k, s - 2^k$
由此可知, 对于任意一个 $s$ , 都可以拆分为 $logs$ 个组, 通过判断选组的情况即可转化为 $01$ 背包 问题
1 | for (int i = 1; i <= n; ++ i) { |
线性多重背包 $O(n)$
我们发现二进制优化的多重背包至多将每个物品分为 $logn$ 个物品, 因此时间复杂度为 $O(n \cdot logn)$. 而多重背包转移具有决策单调性, 使用单调队列可以优化至 $O(n)$ 线性, 详见 $\rm dp$ 优化.
分组背包
将所有物品分为 $n$ 组, 每组物品中最多只能选一个物品.
枚举第 $i$ 组中选第 $k$ 物品即可
可得状态转移方程：
$$f_{i, j} = max(f_{i, j}, f_{i - 1, j - v{i, k}} + w_{i, k})$$
($v_{i, k}$ 表示第 $i$ 组物品中第 $k$ 个物品的体积, 以此类推)
模板：
1 | for (int i = 1; i <= n; i ++) |
依赖背包
选 $A$ 物品需要购买 $B$ 物品, 或选 $A$ 物品才可以买 $B, C$ 物品
基本的解决思路是, 我们将两种绑定的物品转化为分组背包, 举个例子, 若买 $A$ 之后才可以买 $B$, 会出现以下三种情况
- 选 $A$ 不选 $B$
- 选 $A$ 选 $B$
- 不选 $A$ 不选 $B$
对于每一种情况, 进行 $dfs$ 深度搜索绑定为一个组, 再按照分组背包的二进制解即可
我们可以发现, 当有 $n$ 件物品依附于一件物品时, 分出组的个数为 $2^n + 1$ 时间复杂度起飞 ~
当物品的绑定关系较为复杂时, 需要使用 树形$\rm dp$ 解决以上问题
扩展: 输出背包方案
当解决最优化问题时, 题目可能要求输出最优化状态下的方案. 通过记录该状态从哪个状态转移而来, 输出方案时倒推到初始状态即可.
线性动态规划
经典应用：
1. 最长上升子序列
暴力版本 $O(n^2)$
集合
可以用 $f_i$ 表示所有以第 $i$ 个数结尾的上升子序列, 维护的属性是长度最大值 $Max$；
- 那么如何将初始状态转移到 $f_i$ 呢？
我们可以依照 $f_i$ 子序列的倒数第二个数来分类： $0$ 表示当前子序列长度为 $1$, $1$ 表示该子序列的倒数第二个数为总序列第 $1$ 个数 ……以此类推, 直到 $i - 1$ 表示该子序列的倒数第二个数为总序列第 $i - 1$ 个数.
- 如何判断该状态是否成立呢？
对于 $f_i = j$, 只需判断 $a[j] < a[i]$, 如成立则存在该状态
因此得到的状态转移方程为：
$$f_i = max(f_i, f_j + 1)$$
- 该解法的时间复杂度？
状态数量 $O(n)$ * 转移计算量 $O(n)$ = $O(n^2)$
1 | int n, a[N]; |
另外, 也可以将选当前位置和不选当前位置单独分离出一个二维状态
若要记录最长上升子序列, 则将主体部分改为：
1 | int g[N]; |
单调优化版：$O(n \cdot logn)$
观察性质可以发现, 对于
$3$ $1$ $2$ $1$ $8$ $5$ $6$
这个序列, 当枚举以 $8$ 为结尾的最长上升子序列时, 下标为 $1$ 的数字 $1$ 无疑是比下标为 $0$ 的数字 $3$ 更优的选择 (涵盖的值域更大, 更有机会取得最长上升子序列)
因此我们可以开一个数组 $q$ 存储长度为 $i$ 的上升子序列中结尾元素最小的情况中结尾元素的最小值.
$Q & A$
- 该最小值是否随结尾值 $i$ 的增大而严格单调递增？
假设对于长度为 $k$ 的末尾最小值为 $n$ , 若 $n$ 小于或等于等于长度为 $k - 1$ 的末尾的最小值, 则对于 $k - 1$ 必有一种更优的、最小值更小的情况, 则该假设不成立
- 那么如何求出以 $a_i$ 结尾的最长上升子序列的长度的最大值呢？
对于预处理好的不同长度的上升子序列 $q$, 只需在该数组中利用二分查找找到不大于 $a_i$ 的最大的值 $q_k$ , 将 $a_i$ 接在 q[k] 后面即可. 此时还要注意, 由于 $q_k$ 是不大于 $a_i$ 的最大的情况, 所以 $q_{k + 1}$ 的值一定会大于 $a_i$ 因此需要更新 $q_{k + 1}$.
由于对于每个点进行二分查找, 因此该算法的时间复杂度是 $O(n \cdot logn)$
模板：
1 | int n; |
2. 最长公共子序列
集合
使用 $f_{i, j}$ 表示所有 第一个字符串的前 $i$ 个字母构成的子序列 和 第二个字符串前 $j$ 个字母构成的子序列 的公共子序列长度
属性
长度最大值
集合划分
将全集依照 是否选择 $a_i$ 和 $b_j$ 分为四个子集：
$00$：$a_i$ 与 $b_j$ 均不选
$01$：$a_i$ 不选而 $b_j$ 选
$10$：$a_i$ 选而 $b_j$ 不选
$11$：$a_i$ 与 $b_j$ 选
状态表示
对于第一种状态, 可以表示为 $f_{i - 1, j - 1}$
对于第二种状态, 可以表示为 $f_{i - 1, j}$, 但由于 f 数组表示的是子序列长度, 所以并不能达到 “不包含 $a_i$ 而包含 $b_j$ 的情况” . 因此这种情况是包含第一种状态的, 但由于所求属性为长度最大值, 这种冲突并不会影响最终结果
同理, 对于第三种状态, 可以表示为 $f_{i, j - 1}$
对于第四种状态, 可以表示为 $f_{i - 1, j - 1}$
因此, $f$ 的状态计算只需取后三种情况的最大值即可
模板
1 | int n, m; |
时间复杂度 $O(n^2)$
