浅谈 DP 状态的定义及时空优化

· · 算法·理论

前言

DP 的类型各种各样，但也不是完全不同，还是有一些相似点在里面的。

理解

个人认为，\color{red}\text{DP}=\textrm{状态定义}+\textrm{转移方程}+\textrm{优化}，三者缺一不可。其中最关键的是状态定义，走错了第一步，接下来可能就难以回头；即便可以求出答案，可能也会让接下来的步骤增加许多困难。所以，定义DP状态时应当要考虑到状态的转移，这样做，转移方程也会自然而然的列出。而优化，就好像是点睛之笔，原本就巧妙的做法根据某些方法再一次地降低了它的时空复杂度。只有把 \color{blue}\textrm{状态定义} 和 \color{blue}\textrm{优化} 这两步练得熟能生巧，才能在 DP 上取得大的突破。
这里补充一下，为什么作者认为不应该专门训练转移方程的推导。在大家大部分的题解中，应该都是推导转移方程占了大篇幅；但是我认为，转移方程是在选手定义 DP 状态的时候就已经有过思考的，选手在固定了状态时就应当对整道题有一个大致的把握，所以在此时转移方程应该不是难点。可以发现，真正的 DP 难题、巧题，最关键的一步就是状态定义，而题解大多数都是直接给出正解。难道是他们直接就想到了如此巧妙的状态定义吗？我相信大部分都还是走了一些弯路的，只是没有在题解中体现出来。所以作者认为，DP 的状态定义才应当是拿出来讨论的关键，而不应当是 DP 方程的推导。

状态定义

DP 状态的定义，围绕着一个中心思想：

\color{red}\large\textrm{用尽可能小的空间传递尽可能多的关键信息。}

接下来让我们深入探讨一下这句话。首先，我们可以提取出 3 个关键词：

  1. 小的空间
  2. 多的信息
  3. 关键信息

其中，编号越大的词语，它的地位越重。首先，什么样的信息才谈得上是“关键信息”？我的答案是——所有我们需要求的答案、对答案的重要约束以及得到以上两种信息的必要信息。从状态转移的角度来说，这是显然的，因为前两者一旦缺失，将无法得到答案；而必要信息如果缺失，将无法进行转移。至于剩下的那些影响不大的信息，我们本着节约空间的原则，尽可能的就不去存储它们了。当然，想象是美好的，现实是残酷的。常常，题目给出的数据范围并不能让我们存储所有的“关键信息”，我们应当要学会取舍，保留最重要的那些。这便是“多的信息”，用同样的空间，将尽可能重要的那些传递下去。再然后，小的空间即是指在不影响信息量的情况下，让我们的 DP 状态可以用能承受的空间装下来，将能优化的优化掉。大多情况下，小的空间其实也对应了小的时间。
打个形象一点的比方，你面前有一堆金银珠宝和一个背包，首先你需要找到那些价值最大的物品，将他们尽可能多的装进背包里。但是这还不够，你还可以用处理一下那些物品，比如压缩，铸造，浇灌等（当然，这里并不仅仅指的是状态压缩），以达到压缩空间、装更多的物品。再甚至，你可以把背包里无用的针线拆了，从物理上扩大背包的容积。（请读者自行体会这段话与 OI 中的对应关系）

应用

刚刚说了很多理论，接下来讲讲 OI 中的例子。

P1651 塔（DP 入门必做题）
这里列出这道题，是为了告诉大家，如何同时满足“多的关键信息”和“小的空间”。在此题中，我们通过只记录差值的方法，巧妙地存储下了当前的状态。

这里用这道入门题举例，也是为了引入我接下来想说的：其实我们 DP 数组里面的值也是一个信息！ 这一点是极容易忽略的，但是这也是我们解决刚刚那道题的本质。对于暴力做法，f_{i,j} 表示的是左、右两座塔的高度分别是多少，其类型是 bool，所以这种状态包含了 2 个信息（bool 的信息量太弱了，在此题中就不算做一个信息了）；而正解，f_i 表示的是左右两座塔的差值，其类型是 int，所以这种状态也包含了 2 个信息！这告诉我们，合理利用 DP 数组里面的值也是很重要的（这里不是指 bool 就一定不好，至少它拥有更小的常数，是 bitset 优化 DP 的基础）。

NKOJ5991 背包问题+
一句话题意：一道奇怪数据范围的背包板题。1\le n\le200,1\le v,V\le10^6,1\le w\le200。
正常的背包问题状态定义为：f_i 表示体积为 i 的背包可以装下的最大价值。但是这样的时间复杂度为 O(nV)，虽然勉强能过 （我本来以为过不去的，还是没有卡这种做法），但是稍微再加强一下数据就无了。这道题出题人的本意应该是交换下标与 DP 数组的内容，f_i 表示装满价值为 i 的物品需要的最少体积，时间复杂度 O(nW)，轻松通过本题。这是一大类例子，即交换状态与 DP 存储的内容，可能会有奇效。

关键信息的取舍也是一大经典难题，经典代表是插入 DP，即在序列中间插入一个数或者取走一个数。

P5999 [CEOI2016] kangaroo
一道好题，就是不知道为什么只评到了蓝...（对于了解这类套路的人确实很水，但是对于那些没做过这类题的人就有点恶心了）
考虑最终那条路径的编号，很显然是一个 M 型。定义状态 f_{i,j} 表示只填了前面 i 个数，形成的连续的 M 型路径共有 j 条。这样就可以转移了，因为此题的难点在于每次到达的地点是乱序的。而我们通过将路径切割成多条的方式使得整个处理的部分变得有序了。转移方程与具体实现请读者自行思考，必要时可以参考题解，这类题需要真正的去尝试才能切身体会到做法之妙。但这不是本文讨论的重点，故不多赘述。

优化

这又要分类了。我们都知道：

\color{red}\textrm{优化} \begin{cases} \textrm{时间优化}\\ \textrm{空间优化} \end{cases}

接下来让我们依次来谈一谈。

时间优化

\mathscr Part\ 1 思路判断

有了一个 DP 的基本思路，但是发现时间复杂度无法承受。这时，我们首先想到的不应当是直接从式子的角度去优化它，应该先考虑自己的这种做法是否正确。作为一名成熟的 OIer，这一步是一定少不了的。当然了，大家看很多的巨佬做题好像都没有这一步——那是因为，他们要不然就是在最开始通盘考虑时早已想过，要不然就是由于自己的熟练很快的确定了自己的做法是正确的。总之，这一步是缺少不了的。一定要保证在做法正确的情况下，再去考虑其他的优化。

\mathscr Part\ 2 优化模板

关于 DP 的时间优化，有各种各样的模板，如前缀和优化、单调队列优化、斜率优化、四边形不等式优化等。这些模板都是要熟练掌握的，灵活运用它们，可以帮助我们解决大量的问题。至于模板的练习，相信大家都很清楚，这里就不多阐述了，总之就是熟能生巧。另外，还有一些其他的优化方式，例如 线段树优化 DP、bitset 优化 DP 等。

\mathscr Part\ 3 运用题目特性

如果前两步也不能让代码的复杂度达到预期，那可能是题目当中的某些性质还没有被发掘出来。这时，我们就需要再次分析 DP 方程，找到其中的性质，将里面的一部分转移合并或者是省略掉。这是很关键的，因为大多数情况下这里的“省略”可能就达到了 O(n) 甚至是 O(n^2) 的复杂度，这可谓是巨大的优化！

\mathscr Part\ 4 应用

拔河比赛
题意：2 组人，各有 n,m 个，力量 v_i，颜值 w_i，选择一部分，使得这两组人力量之和相同，求颜值之和的最大值。1\le n\le1000,1\le v_i\le1000,-10^9\le w_i\le10^9。
一看，这不是塔吗？？？但是这时间复杂度估计不能承受。正解很妙——由于颜值 v 有正负之分（处理时显然会把第二组的颜值变为负数），而对于单个数的大小只有 1000，所以可以感觉到其实不用跑满 V。此题只需要先一个 random_shuffle 打乱顺序，再跑之前的背包即可，跑的时候为了权衡时间和正确性，可以设计 V\gets v\sqrt n。可以证明，这样的正确性是极高的！这就充分利用的题目特性。

空间优化

\mathscr Part\ 1 时间优化

看到这里肯定会有人疑惑：这两者有什么关系？！事实上，我想表达的是，大多数的题目都只会被时间卡掉，有的时候虽然初始的 DP 方程时空双爆，但是优化掉时间之后会发现空间也被优化掉了。所以，空间优化一定是在时间之后的，它比时间更加灵活。

\mathscr Part\ 2 优化模板

空间优化的常用技巧也有很多，比如滚动数组、记忆化搜索 + map、longlong改int（甚至可以是short） 等。具体的要根据题目来随机应变。这里再谈一下我对状态压缩的理解。本质上，我认为状压好像也并没有压缩空间。我完全可以开一个 n 维、每一位都是 0/1 的 DP 数组来达成一样的效果。在我看来，状压实际上只是方便了我们实现而已，并不像它名字一样真的可以压缩。

\mathscr Part\ 3 运用题目特性

这与时间优化是相似的，不细说了。

\mathscr Part\ 4 应用

卡空间的题真的很少，大家如果遇到了一定要好好对待！

HihoCoder1596 Beautiful Sequence
题目大意：给定一些数（可能相同），将它们随机打乱后构成凹函数，求排列数，n\le60。
这里要谈的是加强版，n\le100。
NKOJ8909 凸
前者的做法这里不予讨论，网上有详细题解；问题是 n 变大之后，时间复杂度 O(n^4) 仍能接受，但空间复杂度接受不了。这里运用到了题目的特性，将对 f_{i,j,k,l} 的贡献改为对 f_{l,k,j,i} 的贡献，已达到控制第一维的值的效果，这样就可以滚动掉第一维，空间复杂度 O(n^3)，可以 AC。

接下来列举一道综合题，在不看题解的情况下，读者可以自己尝试一下有多少种空间优化方法。

P6622 [省选联考 2020 A/B 卷] 信号传递
这题卡空间的过程极为经典，这里引用一篇写得不错的题解。

结语

动态规划作为信息学竞赛中十分重要的一个算法，是需要投入大量精力去练习的。唯有勤奋刻苦，方能展翅翱翔！