动态规划学习笔记

我不会 DP 😭

基本结构

懒得说，只需要记住无后效性和最优子结构就可以了。

模型

简单计数

大多数用到的都是乘法原理和加法原理。

背包

略提一下就可以了。

01 背包

朴素状态：

记 $dp_{i,j}$ 为前 $i$ 个物品容量为 $j$ 时最大贡献，则有：

$$dp_{i,j}=\min(dp_{i-1,j},dp_{i-1,j-w_i}+v_i)$$

发现每一个状态只与上一个状态有关，于是滚动数组优化如下：

$$dp_i=\max(dp_i,dp_{j-w_i}+v_i)$$

滚动数组枚举容量时记得从上往下枚举。

完全背包

每个物品可以选无数次，那么与 01 背包状态相同，则有：

$$dp_{i,j}=\max(dp_{i,j-w_i}+v_i,dp_{i-1,j})$$

多重背包

每个物品可以选 $k_i$ 次，那么就可以把相同的物品看成多件 01 背包的物品。

二进制分组优化

由于拆分一个物品为多个物品时，总是会重复选 $v_i$ 这一过程，于是可以把每个物品拆成 $v_{i,j}(j\in\{0, \lfloor \log k_i+1 \rfloor-1\})$ 来表示有 $2^{j-1}$ 个 $i$ 物品， 那么时间复杂度就变为了 $O(W \sum \log k)$

线性 DP

状态为线性的 DP。

如果想不出来，不妨多加点维数。

区间 DP

注意区间转移是从大到小还是从小到大方便，要不要判断左右端点，是闭区间还是开区间。

有时可以应用倍增的思想。

树形 DP 与图上 DP

顾名思义，可以给后置节点加限制。树上问题可以先开始在链上和菊花图上思考。无向图可以考虑 Tarjan 缩点后在拓扑序上 DP。

状压

状态压缩。

数位

对于大数字的每一位来 DP。常可以被记忆化搜索代替。

优化

前缀/后缀和

提前计算贡献。

二分/倍增

状态有单调性时也许可以用二分。

数据结构

比如可以用线段树来优化要找区间最大的 DP。