基础动规 | Open17's Blog

记忆化

如果能够找到与原问题相似的子问题,我们就能用递归解决

选/不选以及选那些的思路去缩小问题的范围

而所谓DP,本质上就是带备忘录的递归算法

一些变化

对于回溯，通常是在「递」的过程中增量地构建答案，并在失败时能够回退，例如八皇后。对于递归，是把原问题分解为若干个相似的子问题，通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化，就需要 return 一个值并加以保存。

时间复杂度计算: 状态个数*单个状态所需的时间

转为递推, 定义形如 $d p_{i}$ 表示一些元素算得的结果:

确定边界
自树底向上

为什么要转?

两者可视为手动挡和自动挡,自动挡虽然方便,但是灵活性不如手动挡(递推dp)

比如递推形式可以滚动数组优化,可以更方便的加入各种各样的数据结构优化

经典DP

最大子数组和

Kadane算法, 定义 $f_{i}$ 为以 $i$ 结尾的最大子数组和,显然有

f_{i} = m a x (f_{i - 1} + a_{i}, a_{i})

答案为 $max (f_{i})$

网格DP

只能向右或向下移动,经典例子传纸条,从左上角到右下角的路径,定义 $f_{i, j}$ 为到 $(i, j)$ 的路径和,转移方程为

f_{i, j} = f_{i - 1, j} + f_{i, j - 1}

打家劫舍

相邻只能选择一个, 定义 $f_{i}$ 为前 $i$ 个物品的最大价值, 转移方程为

f_{i} = m a x (f_{i - 1}, f_{i - 2} + a_{i})

有环的时候分类讨论是否取第一个即可

最长公共子序列

定义 $f_{i, j}$ 为 $a$ 的前 $i$ 个字符和 $b$ 的前 $j$ 个字符的最长公共子序列长度,转移方程为

f_{i, j} = {\begin{cases} f_{i - 1, j - 1} + 1, & a_{i} = b_{j} \\ m a x (f_{i - 1, j}, f_{i, j - 1}), & a_{i} \neq b_{j} \end{cases}

这个其实可以用bitset优化, 但是我不会, 就不写了

最长上升子序列

定义 $f_{i}$ 为以 $i$ 结尾的最长上升子序列长度,转移方程为

f_{i} = m a x (f_{j}) + 1, a_{j} < a_{i}

答案为 $max (f_{i})$

当然其实这种问题做法很多,还可以二分/排序转换为LCS/序列数据结构优化(如树状数组,线段树)

子数组DP

将数组划分为多个子数组, 然后要求满足一些条件, 求合法/方案/代价最小/最大等

一般定义 $f_{i}$ 表示考虑前缀 $a [: i]$ 的划分问题

然后枚举最后一个划分的位置, 转移方程类似

f_{i} = m a x (f_{j} + c o s t (j + 1, i))

子序列DP

在数组种选择一个子序列, 然后要求满足一些条件, 求合法/方案/代价最小/最大等

一般定义 $f_{x}$ 表示以元素 $x$ 结尾的合法子序列的最长长度/个数/元素和，从子序列的倒数第二个数转移过来注意这里的 x 不是下标，是元素值。如果 x 不是整数，或者值域范围很大，可以用哈希表代替数组。参考s7.4 合法子序列 DP

背包DP

01背包

题意: 有 $n$ 个物品,每个物品有重量 $w_{i}$ 和价值 $v_{i}$ ,背包容量为 $m$ ,求背包能装下的最大价值

定义 $f_{i, j}$ 为前 $i$ 个物品,背包容量为 $j$ 的最大价值,转移方程为

f_{i, j} = m a x (f_{i - 1, j}, f_{i - 1, j - w_{i}} + v_{i})

答案为 $f_{n, m}$

注意到 $f_{i}$ 只和 $f_{i - 1}$ 有关, 所以可以压缩一维

但是注意到转移是从左上角到右下角的, 所以要从大到小枚举i, 否则会错误的使用到更新过的状态

完全背包

完全背包和01背包的区别是每个物品可以选无限次, 所以转移方程为

f_{i, j} = m a x (f_{i - 1, j}, f_{i, j - w_{i}} + v_{i})

答案为 $f_{n, m}$

这里压维的时候无需倒序枚举,因为错误使用更新过的状态,等价于无限选择

多重背包

每个物品有数量 $c_{i}$ , 不难想到转移方程为

f_{i, j} = m a x (f_{i - 1, j}, f_{i - 1, j - k * w_{i}} + k * v_{i})

如果你看过前面的基本功章节,你应该能想到倍增那章引用OI WIKI的原话:

我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在 k 的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过「任意整数可以表示成若干个 k 的次幂项的和」这一性质，使用之前求出的代表值拼成所需的值。

这里选择k后的贡献显然是个解析解,所以不需要倍增计算,但是可以同样的思路对 $c_{i}$ 二进制拆分

那么此时可以把一个物品拆分为 $l o g_{c_{i}}$ 组01背包

混合背包

前三种都有, 所以分类讨论即可

二维费用背包

01背包加一维就可以了

分组背包

每个物品属于一个组, 组内只能选一个

我们压掉同组物品的维度, 设 $f_{g, j}$ 表示处理完前 $g$ 组、容量不超过 $j$ 的最大价值。

第 $g$ 组物品集合为 $S_{g} = {(v_{k}, w_{k})}$ 。

那么转移方程为：

f_{g, j} = max (f_{g - 1, j}, max_{\begin{matrix} (v_{k}, w_{k}) \in S_{g} \end{matrix}} f_{g - 1, j - v_{k}} + w_{k})

你会发现, 这形式不还是一个01背包吗?所以还可以再压一维

这个时候一定要小心别让同一组的物品相互影响转移

建议按照下面顺序来循环:

枚举组
枚举背包容量(倒序)
枚举物品

这样不用额外复制数组

树形DP

树的直径

树上任意两点距离的最大值

考虑贡献:

如果直径经过根节点, 则为树的子节点的最大深度+次大深度
如果直径不经过根节点, 则为根节点的子树的最大直径

这样转移即可

换根DP

两次扫描，换根dp, 思考根转移对于整体答案变化的贡献

对于一些指定一个根很好计算，但是需要遍历全部根的问题，我们可以指定一个根计算，然后思考根从该节点转移到另一个节点的贡献是什么，从而进行DP转移

更严谨的说：

换根DP是树形DP的一种特殊情况，它解决的是当树的根节点发生改变时，树的状态发生的变化问题。在换根DP中，我们需要考虑树结构的变化对计算结果的影响。

树上最大独立集

最大独立集即为选择尽可能多的点，并且这些点不相邻

树形DP的转移还是一样思考，思考原问题与子问题的关系，然后转移：

选/不选枚举选哪个

树上最小支配集

最大独立集反过来

树形DP的转移还是一样思考，思考原问题与子问题的关系，然后转移：

选/不选枚举选哪个不过最小支配一般要分类讨论一下，有时候推广到一般树规律比较复杂，可以从二叉三叉开始思考

状态机DP

定义 $f_{i, j}$ 表示考虑前缀 $a [: i]$ 的状态机问题, 其中 $j$ 表示当前状态

然后按照状态机转移 $j$ 即可

数位DP

用于解决在一个区间内满足某些条件的数的数量问题

这类题目比较固定, 直接使用下面的模板即可

cpp

// https://leetcode.cn/problems/numbers-with-repeated-digits/solutions/1748539/by-endlesscheng-c5vg/
// 0x3f v1.0
int numDupDigitsAtMostN(int n) {
    auto s = to_string(n);
    int m = s.length(), memo[m][1 << 10];
    memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
    function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int {
        if (i == m)
            return is_num; // is_num 为 true 表示得到了一个合法数字
        if (!is_limit && is_num && memo[i][mask] != -1)
            return memo[i][mask];
        int res = 0;
        if (!is_num) // 可以跳过当前数位
            res = f(i + 1, mask, false, false);
        int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
            if ((mask >> d & 1) == 0) // d 不在 mask 中
                res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
        if (!is_limit && is_num)
            memo[i][mask] = res;
        return res;
    };
    return n - f(0, 0, true, false);
}

区间DP

一般定义 $f_{i, j}$ 表示区间 $[i, j]$ 的最优值

然后枚举分割点, 转移方程类似

f_{i, j} = m a x (f_{i, k} + f_{k + 1, j} + c o s t (i, j))

同时较常见的是k=1时, 等价于对区间尝试左/右扩展, 转移方程类似

f_{i, j} = m a x (f_{i + 1, j} + c o s t (i, i + 1), f_{i, j - 1} + c o s t (j, j - 1))

其中 $c o s t (i, j)$ 表示区间 $[i, j]$ 的合并代价

实际通常将j转换为i+len-1,通过枚举len来从小到大转移

SOSDP

当 一个集合的答案依赖于它所有子集的答案 时，可以使用 SOS DP 来加速计算。

一般适用于 $n \leq 20$ 左右的情形（因为状态数为 $2^{n}$ ）。

设 $g [m a s k]$ 表示集合 mask 的答案。
我们可以通过枚举每一位，将子集的贡献逐步传递到超集，例如对于子集和问题

g [m a s k] = \sum_{T \subseteq m a s k} f [T]

可以这样转移:

cpp

for (int i = 0; i < n; i++) {
    for (int mask = 0; mask < (1<<n); mask++) {
        if (mask & (1<<i)) {
            g[mask] += g[mask ^ (1<<i)];
        }
    }
}

记忆化 ​

经典DP ​

最大子数组和 ​

网格DP ​

打家劫舍 ​

最长公共子序列 ​

最长上升子序列 ​

子数组DP ​

子序列DP ​

背包DP ​

01背包 ​

完全背包 ​

多重背包 ​

混合背包 ​

二维费用背包 ​

分组背包 ​

树形DP ​

树的直径 ​

换根DP ​

树上最大独立集 ​

树上最小支配集 ​

状态机DP ​

数位DP ​

区间DP ​

SOSDP ​

记忆化