DDOSvoid's Blog

浅谈动态规划

发表于 更新于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

简介

总感觉这个标题好像有点大

DP数组变量的处理

对于 $dp$ 数组 $f[i][j]=k$，我们定义 $i$ 和 $j$ 为状态变量，$k$ 为答案变量

一般情况下，状态变量都不止一个，答案变量一般为一个

首先我们来考虑答案变量，毕竟状态变量有几个都不重要

我们最常见的在同一个状态下有多个答案变量的情况就是最优解和方案数，这个有太多例子就不单独列举了

以下还有几种比较特殊的情况

以 Luogu P3052 [USACO12MAR]Cows in a Skyscraper G 为例，我们定义 $f[i]$ 表示最小的分组，同时又定义 $g[i]$ 表示在 $f[i]$ 情况下，最后一组的空间最多剩下多少

能够注意到这个例子中的两个答案关系和第一个例子中的最优解和方案数的例子的关系类似

两个答案变量中的一个变量对另一个变量有一个依赖关系

我们定义为其为主变量和副变量，其中副变量对主变量有依赖关系，即如果主变量得到更新则副变量必须进行重新赋值

当然还有更加一般的情况，以 Luogu P4067 [SDOI2016]储能表 为例，我们在记忆化搜索的时候记录了两个答案变量，一个是方案数，另一个是和，这两个变量之间并没有特殊的关系，只是对应状态下的两个答案变量而已

例题

  1. 部分题目可能只询问在主变量满足一定条件的情况下，副变量的最值

    CF 900E Maximum Questions

DP中的排序

一部分线性 $dp$ 需要在 $dp$ 之前对数组进行排序

为什么需要排序？

  1. 避免后选的影响先选的

    Luogu P6146 [USACO20FEB]Help Yourself G

  2. 要求最优化情况下，必须按照一定的顺序选择

    以 Luogu P4138 [JOISC2014]挂饰 为例，我们以 $f[i][j]$ 表示前 $i$ 个挂饰，有 $j$ 个挂钩的最大收益

    但是在 $dp$ 之前我们要将挂饰按照挂钩数量进行排序

    以 Luogu P2577 [ZJOI2004]午餐，为例，我们以 $f[i][j]$ 表示前 $i$ 个人，第一队的打饭总时间为 $j$ 的最短时刻

    由于打饭总时间一定，所以吃饭时间长的人一定放在前面，所以我们要按照吃饭时间从大到小排序

DP中状态定义的拓宽

以最简单的 $01$ 背包为例，我们在定义状态时令 $f[m]$ 为装了重量为 $m$ 的最大值

但是实际上我们可能并没有把背包装满，换句话说，我们定义的状态并非是恰好装了 $m$，而是装了小于等于 $m$，从我们最终的答案输出只需要输出 $f[m]$ 也可以看出

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 1; i <= n; ++i)
    for (int j = m; j >= w[i]; --j)
        f[j] = max(f[j], f[j - w[i]] + c[i]);
cout << f[m] << endl; 

for (int i = 0; i <= m; ++i) f[i] = -INF; f[0] = 0; 
for (int i = 1; i <= n; ++i)
    for (int j = m; j >= w[i]; --j)
        f[j] = max(f[j], f[j - w[i]] + c[i]);
int ans = 0;
for (int i = 1; i <= m; ++i) ans = max(ans, f[i]);
cout << ans << endl;

这种做法的优势在于可以优化状态的大小，或者改变 $dp$ 转移的方式从而优化复杂度，拓宽后的状态常常需要用到继承

优化状态

Luogu P4138 [JOISC2014]挂饰，$f[i][j]$ 的第二维我们定义为有大于等于 $j$ 个挂钩，因为题目并没有规定挂钩的数量上限，但是挂钩最多只用 $n$ 个即可

优化复杂度

Luogu P2519 [HAOI2011]problem a，我们定义 $f[i]$ 扫到 $i$ 为止的最大值，而不是选的最后一个区间的右端点

DP数组的继承

我们最先接触到的例子就是 $O(n^2)$ 求解最长公共子序列，其中我们定义 $f[i][j]$ 表示第一个序列匹配到第 $i$ 位，第二个序列匹配到的第 $j$ 位的最长公共子序列的长度

1
2
3
4
5
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]); // 这句就是继承
        if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
    }

继承比较有用的一方面就是可以优化复杂度，以 Luogu P2519 [HAOI2011]problem a 为例，我们定义 $f[i]$ 扫到 $i$ 为止的最大值，$f[i]$ 在更新的时候先继承 $f[i - 1]$ 的值，原本的 $dp$ 的复杂度为 $O(nlogn)$，因为要在前缀中寻找最大值，而我们直接继承也就省掉了这件事情

DP状态转移拆解

$dp$ 中的一个状态可能由多个元素组成，一次状态的转移可能需要每个元素都做一次转移，这样会导致枚举下一个状态的复杂度过高，这时候可能考虑一次只转移一个元素

hdu 5807 Keep In Touch

DP状态转移限制

简单来讲，$dp$ 状态之间能够转移的条件就是 $dp$ 状态转移限制

平时做题中我们最常见的状态转移限制就是 $j<i$

对 $dp$ 进行优化的方法之一就是对于每个状态能够快速找到满足这个状态的限制的其它状态的最大值、最小值或者是和

一般情况下我们直接使用数据结构来存储满足限制的所有状态，这种直接使用数据结构的技巧就不再赘述

一种比较 $trick$ 的方法是将满足限制的状态分成两部分，一部分使用数据结构进行存储，另一部分直接暴力枚举判断

以 CF 1427C The Hard Work of Paparazzi 为例