动态规划题目

Published: April 30, 2019 by Daltao

• Categories:
• problems 4

• Tags:

• 动态规划求和问题
• 背包问题
  • 01背包
  • 完全背包
  • 多重背包
  • 超大背包
• 带修改动态规划
  • 序列带修改带区间查询动态规划
  • 树上带修改带路径查询动态规划
• 一些合成问题
• 动态规划去后效性
• 决策单调性
  • 区间DP和决策单调性
• 线性DP的优化
• 箱子堆叠问题
• 数位DP
• 一些离散状态的DP
• DP与拓扑序
• 整数和浮点数DP
• 状压DP和排列
• 区间DP
• 分治+FFT
• 树上卷积式DP
• 参考资料

动态规划求和问题

考虑有这样一个$n\times m$的矩阵$M$，$1\leq n,m \leq 3000$。矩阵$M$代表一个迷宫，$M_{ij}$为1表示该处不可通行，为0表示该处可通行。玩家只能每次向右或向下移动一格。

迷宫的出口和入口信息现在还不确定，每个为0的位置都有可能为入口和出口。

记$f(i,j,u,v)$表示入口为$(i,j)$，出口为$(u,v)$时，有多少可能的从入口到出口的轨迹，现在我们希望求：

$$\sum_{M_{i,j}=0}\sum_{M_{u,v}=0}f(i,j,u,v)$$

一般的动态规划每趟可以给出$O(nm)$的时间复杂度，但是由于总共要执行$O(nm)$次，因此总的时间复杂度将达到$O(n^2m^2)$。

我们考虑进行优化，实际上观察正常的动态规划递推公式：

$$dp(i,j)=dp(i-1,j)+dp(i,j-1)$$

我们可以发现，对于不管入口和出口怎么变换，递推关系都是不会改变的。并且还有最重要的一点，就是递推关系是线性的。

现在我们定义$dp_{i,j}$为当我们选择$(i,j)$作为入口的动态规划公式。这时候我们再定义一个新的函数:

$$g=\sum_{M_{i,j}=0}dp_{i,j}$$

那么我们实际上要求的是：

$$\sum_{M_{i,j}=0}\sum_{M_{u,v}=0}f(i,j,u,v)\\ =\sum_{M_{i,j}=0}\sum_{M_{u,v}=0}dp_{i,j}(u,v)\\ =\sum_{M_{u,v}=0}\sum_{M_{i,j}=0}dp_{i,j}(u,v)\\ =\sum_{M_{u,v}=0}g(u,v)$$

下面我们证明$g$也满足递推关系$g(i,j)=g(i-1,j)+g(i,j-1)$。

$$g(i,j)=\sum_{M_{i,j}=0}dp_{i,j}(i,j)\\ =\sum_{M_{i,j}=0}[dp_{i,j}(i-1,j)+dp_{i,j}(i,j-1)]\\ =\sum_{M_{i,j}=0}dp_{i,j}(i-1,j)+\sum_{M_{i,j}=0}dp_{i,j}(i,j-1)\\ =g(i-1,j)+g(i,j-1)$$

新的算法的时间复杂度为$O(nm)$。

所以以后遇到这种多个动态规划，但是每个动态规划除了初始状态不同外，递推关系一致，并且我们最终要对其进行求和的问题，我们都可以用这种方式进行加速。

背包问题

01背包

一般的背包问题定义是这样的。给定$n$个正整数$A=a_1,\ldots,a_n$，以及另外一个正整数，判断是否存在一个$A$的子集$S$，子集中的所有数之和恰好等于某个给定的整数$m$。

我们可以定义一个简单的DP，记$f(i,j)$表示前$i$个数是否存在一个子集之和等于$j$。那么我们要求的就是$f(n,m)$。这个函数的转移非常简单$f(i,j)=f(i-1,j)\lor f(i-1,j-a_i)$。因此时间复杂度为$O(nm)$。

但是这里我们可以利用bitset技巧，将时间复杂度优化到$O(\frac{1}{32}nm)$。

完全背包

如果01背包中提到的每个数$a_i$都可以使用无穷次，问是否存在一个$A$的多重集合$S$，集合中的所有数之和恰好等于某个给定的整数$m$。

我们可以定义这样一个简单的DP，记$f(i,j)$表示前$i$个数中是否存在一个多重子集之和等于$j$。我们要求的就是$f(n,m)$，且我们可以推出递推公式：$f(i,j)=f(i-1,j)\lor f(i,j-a_i)$。这里我们$O(nm)$求解这个问题

多重背包

如果01背包中提到的每个数$a_i$可以使用最多$b_i$次，问是否存在一个$A$的多重集合$S$，集合中的所有数之和恰好等于某个给定的整数$m$。

很容易想到一个$O(nm^2)$的做法。但是我们会发现DP公式$f(i,j)$的值始终是布尔值，这实在有些浪费，我们可以为每个状态都额外携带一些信息（这实际上是非常重要的DP设计的技巧）。我们定义一个新的DP公式$g(i,j)$表示仅考虑前$i$个元素，至少需要在前$i$个元素的多重子集中出现多少次$a_i$，才能得到总和为$j$。这样我们就发现了一个转移，如果$g(i-1,j)\leq b_{i-1}$，那么$g(i,j)=0$，否则$g(i,j)=g(i,j-b_i)+1$。这样一来，我们的DP时间复杂度就优化到了$O(nm)$。

有了上面提到的技术，实际上我们可以优化一类01背包问题。记$C=\sum_{i}a_i$，我们可以发现$A$序列中最多只有$\sqrt{C}$个不同的值，因此我们可以将相同值合并得到一个多重背包问题，这样我们就可以在$O(m\sqrt{C})$时间复杂度内求解了。如果$C=O(n)$，那么时间复杂度可以优化为$O(m\sqrt{n})$。

其实上面提到的多重背包公式，泛用性并不是很强，因为DP公式的函数值被用来记录一个无用信息，这个信息只是帮助我们实现$O(nm)$时间复杂度的。比如说我们现在修改一下问题，要求求出所有多重集合中，和正好为$m$的包含最少元素的多重集合大小，就会发现上面提到的DP公式就失效了。下面介绍一种更加泛用的多重背包解决方案。

记录$h(i,j)$表示仅考虑前$i$个$A$中的数，总和为$j$至少需要选择多少元素。这样我们在考虑第$i$个元素的时候，可以根据对于模$a_i$余数不同的$j$分成不同的组进行计算，这样我们会发现，问题就变成了有两个数组$x$（对应$h(i-1,?)$）和$y$（对应$h(i,?)$），其中$y_i=i+\min_{i-b_i-1\leq j\leq i}(x_j-j)$。我们实际上可以维护一个单调队列来解决这个问题。

提供一道题目。

超大背包

题目1：有重量为$1$到$8$的8类物品，种类为$i$的物品总共有$a_i$个。要求找到一组系数$b_1,\ldots,b_n$，满足$0\leq b_i\leq a_i$，且$\sum_{i=1}^8ib_i\leq m$，且要求$\sum_{i=1}^8ib_i$最大。其中$0\leq a_i\leq 10^{16},1\leq m\leq 10^{18}$。

提供一道题目。

这个题目很明显是一个背包，但是背包的容量超大，没法直接DP。

但是我们发现1到8这8个数的最大公倍数仅为840。这意味着对于最优结果，第i个数被选择了$c_i$个，那么$c_i=\frac{840}{i}\cdot a_i+b_i$，其中$b_i< \frac{840}{i}$。

我们发现取$840/i$个$i$的和都是$840$，我们可以把这些值做一致处理，简单称为单元。考虑不由单元组成的部分$\sum_{i=1}^8ic_i$，其一定不超过$840\cdot 8$，也就是说我们可以对这一部分进行DP，$dp(i)$表示取一些数总和为$i$的前提下，最多能保留多少单元。显然单元越多能组成的数范围越大。

最后暴力枚举结果中不能由单元提供的额外部分，同时判断最优解即可。

题目2：有$n$个物品，第$i$个物品的重量为$w_i$，价值为$v_i$，数量无限。有一个承重为$m$的背包，要求计算背包最多能装下多少价值的物品。其中$1\leq w_i\leq 10^3=W$,$1\leq n\leq 10^6$,$0\leq v_i\leq 10^9$，$1\leq m\leq 10^{18}$，且保证结果范围不超过$10^{18}$。

提供一道题目。

可以发现实际上最多考虑$W$个商品，因为相同重量的物品只需要考虑价值最大的商品。

我们可以记录$dp(i)$表示大小为$i$的背包最多能携带价值。一般的dp公式是$dp(i)=\max_{j=1}^ndp(i-w_j)+v_j$，这样做的时间复杂度是$O(nm)$。

有一种优化的方式，就是我们找一个性价比$\frac{v_k}{w_k}$最高的物品$k$，我们知道其余选中物品的某个子集中重量和一旦能整除$w_k$，我们可以将它们全部替换为物品$k$，得到更高的价值。因此我们知道其余物品中的任意子集的重量和不能整除$w_k$。

但是我们知道$x$个整数中$a_1,\ldots,a_x$，必定有个子集的和能整除$x$。假设不存在这样的子集，记$S_i$表示前$i$个整数的和，则$S_1,\ldots,S_x$中每个数的值均落在$1$到$x-1$之间。根据鸽巢定理可知，一定有两个数相同，即$S_i=S_j$，其中$i\lt j$。因此我们可以发现$a_{i+1},\ldots,a_x$的和$S_j-S_i$能整除$x$。

因此我们发现除了物品$k$外其余物品最多选择$w_k-1$个，这样时间复杂度就达到了$O(W^3)$，还是慢了。

这里讲一个天秀的做法。

我们使用第一种做法中提到的dp，但是转移不同。具体的转移如下：

• 背包中什么都不放
• 背包中放一个商品
• 背包中放至少两个商品。这时候我们可以将背包分成两个背包的和，即$dp(s)=dp(i)+dp(s-i)$。

假如我们背包大小为$x$，那么我们可以将背包拆分为两个大小差不超过$W$的子背包。因此我们要计算$[s,s]$，需要依赖状态$[\lfloor \frac{s}{2} \rfloor-W(1-\frac{1}{2}),\lfloor \frac{s}{2} \rfloor+W(1-\frac{1}{2})]$。而这些状态，则依赖于$[\lfloor \frac{s}{2^2} \rfloor-W(1-\frac{1}{2^2}),\lfloor \frac{s}{2^2} \rfloor+W(1-\frac{1}{2^2})]$。总结就是我们需要计算满足下面条件的状态：

$$[\lfloor \frac{s}{2^i} \rfloor-W(1-\frac{1}{2^i}),\lfloor \frac{s}{2^i} \rfloor+W(1-\frac{1}{2^i})]$$

其中$0\leq i\leq \lceil \log_2 s\rceil$。因此可以发现状态的上限为$2W(\lceil \log_2 s\rceil+1)$。而每个状态的计算时间复杂度为$O(W)$，因此总的时间复杂度为$O(W^2\log_2s)$。

由于我们状态比较离散，一种简单的方式就是用哈希表来存状态。但是常数会比较大。

还有一种方式就是用$\log_2s$个长度为$2W$的数组来记录。每次我们深度$i$和$s$传入进行查询。但是在小数据的时候会有问题，解决方案就是暴力计算大小不超过$W$的背包。因此总的时间复杂度为$O(W^2\log_2)$，不变，但是常数变小了。

题目3：给定$n$个非负整数$x_1,\ldots,x_n$，计算总和最大的子集，且子集和不能超过$C$。其中$M=\max_{i=1}^nx_i\leq 1000$，$1\leq n\leq 10^5$，$1\leq C\leq 10^8$。

正常的做法的时间复杂度为$O(nC)$，或是$O(n^2M)$。但是根据论文《Linear Time Algorithms for Knapsack Problems with Bounded Weights》中提到的算法，可以优化到$O(nM)$。

带修改动态规划

序列带修改带区间查询动态规划

题目1：给定一个序列$a_1,a_2,\ldots,a_n$。现在要求处理$q$次请求，每个请求分为两种操作：

• 给定$l,r$，要求从$a_l,a_{l+1},\ldots,a_r$中选取若干个不相邻的元素，使得总和最大
• 给定$i,y$，将$a_i$修改成$y$。

首先如果没有修改且查询区间总是整个的序列的话，我们而已用动态规划来解决这个问题。但是现在又有修改又有区间查询，怎么搞。

先来考虑分治思想，我们将整个序列一分为二，分为左序列和右序列。之后我们独立计算左序列和右序列，之后我们将左右序列合并起来。合并的方式非常简单，左右子序列都维护一个大小为$2\times 2$的矩阵$m$，我们只需要利用修改后的矩阵乘法将两个矩阵乘起来即可。。

可以看出上面的方式只是解决了$l=1,r=n$的查询，那么对于多个任意查询如果回答。我们可以将分治过程理解成一棵树，这棵树中满足父顶点所处理的区间不完全落于$[l,r]$中，但是该顶点落在$[l,r]$中的顶点数上限是$2\log_2n$个，因此我们统计这$2\log_2n$个顶点上的处理结果就可以回答请求。这样回答所有请求的时间复杂度

上面提到的技术叫做离线二分。

好了，现在我们知道怎么解决查询了，但是如果处理修改呢，离线二分就解决不了这个问题了。但是细细的想，你会发现离线二分得到的二叉树实际上与线段树非常雷同。实际上，我们可以直接用线段树来替代离线二分得到的树。这样的好处是什么，线段树每次上传下传标记都是在线的，换句话说，我们只需要为线段树设计一套快速的合并算法，利用线段树天然支持修改的特性，我们就可以支持修改操作了。

这里用的合并算法实际上还是维护$2\times 2$矩阵，通过修改后的矩阵乘法来合并。

利用线段树我们就可以实现$O(\log_2n)$处理每个请求。

提供一道题目。

树上带修改带路径查询动态规划

题目2：给定一个拥有$n$个顶点的树，第$i$个顶点上标着一个数字$a_i$。现在要处理$q$次请求，每个请求分为两种操作：

• 查询树上的最大权独立集
• 给定$i,y$，将$a_i$修改成$y$。

这个问题实际上是问题1的树上加强版本。

如果没有修改操作，我们只需要在树上跑一次DP即可。现在多了修改操作，我们来看看怎么解决。

现在的问题是修改了后标记没法上传，我们可以对整棵树进行轻重链剖分，之后我们发现一条重链上的顶点恰好对应线段树的一个区间。我们可以在这个区间上跑真动态规划，这样我们可以立刻得到以重链顶部顶点为根的子树下的结果。这还不够，我们还需要将结果上传到父亲顶点上去，这里是直接暴力上传。可以发现由于沿着重链不断上升，总的上传次数被约束在$O(\log_2n)$，而每次的时间复杂度为$O(\log_2n)$，因此一次修改的时间复杂度为$O((\log_2n)^2)$。

这里提供一道题目。

一些合成问题

题目1：给定$n$块宝石，第$i$块宝石的等级为$l_i$（$l_i\leq n$），价格为$c_i$。等级为$i$的宝石的出售价格为$p_i$。任意两块$i$级宝石可以合成为一块$i+1$级宝石。问最大收益是多少，这里的收益是出售宝石的收入减去购买宝石的支出。$n\leq 2000$

首先我们按照宝石等级进行排序。之后建立动态规划$dp(i,j)$表示前$i$块宝石，手上等级$l_i$的石头还剩下$j$块，此时的最大收益。

动态规划的转移非常简单，这里不细说。总的时间复杂度是$O(n^2)$。

题目2：给定$n$块宝石，第$i$块宝石的等级为$l_i$（$l_i\leq n$），价格为$c_i$。等级为$i$的宝石的出售价格为$p_i$。任意两块$i$级宝石可以合成为一块$i+1$级宝石。问最大收益是多少，这里的收益是出售宝石的收入减去购买宝石的支出。特殊要求如果购入的宝石是$i_1,i_2,\ldots,i_k$，那么要求$l_{i_1}\leq \ldots \leq l_{i_k}$。$n\leq 2000$

现在我们不能对宝石进行排序。建立动态规划$dp(t,i,j)$表示仅考虑等级不超过$t$的宝石，第$i$块宝石是最后收购的宝石，且手头还剩下$j$块$t$级别宝石的最大收益。

可以发现总共有$O(n^3)$个状态，但是会发现在处理出$dp(t,i,n)$后，之后的有效状态随着$t$的增大1会减少一半。因此真实的时间复杂度还是$O(n^2)$。

动态规划去后效性

动态规划有时候转移需要考虑当前状态的信息，考虑的信息越多，所需要记录的也越多，时间复杂度和空间复杂度也会对应提高。在最严重的时候应该就是需要做状压的时候了。下面介绍一种技术，在一些情况下可以让你摆脱状压带来的时空复杂度飙升问题。

考虑这样一个题目，给定一个$n\times n$的矩形，我们希望在上面放入一些棋子，每个棋子都可以攻击对角线上的其他棋子，现在希望你回答，正好放$k$个棋子，有多少种方案数。

首先我们可以将这道题旋转45度，之后原本对角线攻击现在就对应变成了沿着垂线或水平线攻击。但是由于得到是一个棱形，因此没法直接用组合数学的方式直接跑。一种简单的方式就是状压DP，之后逐行处理，这里有一个技巧，就是偶数行和奇数行可以独立处理，且它们的有效列集合没有并集。这样做的时间为$O(n^22^n)$。

上面的这个算法由于使用了状压，可以看到时间复杂度中出现了一个指数函数$2^n$。当$n$达到$20$或更大的时候，上面的算法就过不了了。

下面说一下如果去除状压。我们重新排列行顺序，注意到这不会影响答案的有效性。我们按照行的长度从小到大进行排序。之后我们会发现一个非常有趣的事情，由于第$i$行始终比前面$i-1$行都长，因此如果前面$i-1$行共放置了$j$个棋子，那么第$i$行中仅有$j$个单元格不能被放置，而其余的单元格都可以放置。因此我们可以定义一个函数$f(i,j)$，其表示前$i$列放置$j$个棋子的方案数，那么可以直接得出一个简单的转移关系$f(i,j)=f(i-1,j)+f(i-1,j-1)\cdot (L_i-j+1)$。这样我们就可以摆脱了可怕的状压，时间复杂度降低为$O(n^2)$。

决策单调性

考虑这样一个DP公式

$$dp(i,j)=\min_{k\leq j}dp(i-1,k)+cost(k,j)$$

这是一个非常常见的递推公式，其中$0\leq i< n$，而$0\leq j<m$。这类公式的空间复杂度为$O(nm)$，时间复杂度为$O(nm^2)$。

如果$m\geq 10^5$，那么这个时间复杂度就太大了。可以尝试判断是否满足决策单调性，即$j\geq k\Rightarrow opt(j)\geq opt(k)$，其中$opt(j)$表示$dp(i,j)$从$dp(i-1,opt(j))$转移而来。如果满足，那么我们还可以用分治的方法来完成。设区间$[l,r]$在函数$opt$的作用下，值域为$[L,R]$。那么我们可以选择$l$与$r$的中点$m$，并暴力枚举值域，找到最优点$opt(m)$，之后递归处理$[l,m)$（它的值域为$[L,p(m)]$）和$(m,r]$（它的值域为$[opt(m),R]$）。可以证明每一层的时间复杂度均为$O(m\log_2m)$，因此总的时间复杂度为$O(nm\log_2m)$。

对最小化DP：

• 对于任意$k<j<i$，都有$cost(k,i+1)-cost(k,i)\geq cost(j,i+1)-cost(j,i)$。则可以使用决策单调性，即$opt(i)\leq opt(i+1)$。
• 对于任意$k<j<i$，都有$cost(k,i+1)-cost(k,i)\leq cost(j,i+1)-cost(j,i)$。则可以使用反向决策单调性，即$opt(i)\geq opt(i+1)$。

而要对最大化DP应用：

• 对于任意$k<j<i$，都有$cost(k,i+1)-cost(k,i)\leq cost(j,i+1)-cost(j,i)$。则可以使用决策单调性，即$opt(i)\leq opt(i+1)$。
• 对于任意$k<j<i$，都有$cost(k,i+1)-cost(k,i)\geq cost(j,i+1)-cost(j,i)$。则可以使用反向决策单调性，即$opt(i)\geq opt(i+1)$。

有时候cost不好直接缓存计算，但是支持$O(1)$从$cost(l,r)$变为$cost(l\pm 1,r)$和$cost(l,r\pm 1$)。仔细观察决策单调性的过程，会发现这时候在一次递归计算过程中，$cost(l,r)$的$l,r$总共移动仅$O(m\log_2m)$次。因此不会影响最终的时间复杂度。

题目1：给定一个序列$a_1,\ldots,a_n$，其中$1\leq a_i\leq n$。记子序列$a_l,\ldots,a_r$的费用为$cost(l,r)=\sum_{i=l}^r\sum_{j=i+1}^n [a_i=a_j]$，即子序列中有多少相同的元素对。现在我们希望将整个序列切分为$m$个非空子序列，要求所有切分的子序列费用总和最小。输出最小费用。其中$n\leq 10^5, m\leq 100$

显然这个问题满足决策单调性。

提供一道题目。

题目2：给定一个序列$a_1,\ldots,a_n$，其中$1\leq a_i\leq n$。记子序列$a_l,\ldots,a_r$的费用为$cost(l,r)=\max_{l\leq i\leq r}a_i-\min_{1\leq i\leq r}a_i$。现在我们希望将整个序列切分为$m$个非空子序列，要求所有切分的子序列费用总和最小。输出最小费用。其中$n\leq 10^5, m\leq 100$

这个问题和问题1的做法雷同，但是注意的是这里的单调性是反向的，即$j\geq k\Rightarrow p(j)\leq p(k)$。

题目3：给定一个序列$a_1,\ldots,a_n$，其中$1\leq a_i\leq n$。记子序列$a_l,\ldots,a_r$的费用为$cost(l,r)=(\sum_{i=l}^ra_i)^k$。现在我们希望将整个序列切分为$m$个非空子序列，要求所有切分的子序列费用总和最小。输出最小费用。其中$n\leq 10^5, m\leq 100$，其中$1\leq k\leq 4$，$0\leq a_i\leq 10^9$。

这种模型具有决策单调性，即$k\leq j\Rightarrow p(k)\leq p(j)$。

时间复杂度为$O(mn\log_2n)$。

题目4：给定$n$个位置，第$i$个位置在$x_i$处，有$y_i$个住户。现在希望建立$k$座信号站。定义每个住户的惩罚为到最近信号站的距离的平方，现在希望所有住户惩罚和最小，问最小的惩罚和是多少。其中$1\leq n\leq 10^5$,$1\leq k\leq 100$，$x_i\lt x_{i+1}$。

提供一道题目。

我们定义$cost(l,r)$表示在位置$l$到位置$r$之间建立建立一座信号站，它们的最小总惩罚。可以发现这个值满足决策单调性。稍微证明一下：

考虑$cost(k,i+1)$的信号站位置为$b$，而$cost(k,i)$的信号站位置为$a$，$cost(j,i+1)$的信号站位置为$d$，而$cost(j,i)$的信号站位置为$c$。不难得到$a\leq c$且$a\leq b$且$c\leq d$。我们可以可以令$d=\max(b,c)$。这时候我们就有$cost(k,i+1)-cost(k,i)\geq cost(j,i+1)-cost(j,i)$的成立。

区间DP和决策单调性

有时候我们会计算区间DP。其中$dp(l,r)=\min_{l\lt i\leq r}f(l,i,r)$。这样的DP的时间复杂度一般都是$O(n^3)$。但是如果区间DP满足$opt(l,r-1)\leq opt(l,r)\leq opt(l+1,r)$，那么我们往往可以将区间DP优化到$O(n^2)$。

原理如下，我们可以根据区间的长度从小到大计算DP值，这样的好处是在计算$l,r$的时候$l,r-1$和$l+1,r$已经被计算完成了。而我们可以在$opt(l,r-1)$和$opt(l+1,r)$之间暴力枚举$opt(l,r)$。可以发现对于每个固定的长度，暴力枚举的量实际上是不会超过$2n$的。因此总的时间复杂度为$O(n^2)$。

提供一些题目：

• Knuth Division

线性DP的优化

有些DP拥有递推性质，比如，我们用DP求斐波那契数列的第$n$项。记$f(n)$表示斐波那契数列的第$n$项，则有$f(n)=f(n-1)+f(n-2)$。由于是递推数列，所以我们可以把后面的$2$项作为向量维护，这样就可以用矩阵来快速计算了。

$$\left[ \begin{array}{cc} 1 & 1\\ 0 & 1 \end{array} \right]^n \left[ \begin{array}{c} 1\\ 0 \end{array} \right]$$

有些DP它的递推关系是线性的，这种情况下也可以用矩阵快速幂。比如考虑这样一个DP：

$$dp(i,j)=\sum_{k=1}^ma_{j,k}dp(i-1,k)$$

这样我们可以构建一个大小为$m$的方阵$A$，其中第$i$行第$j$列的向量为$c_{i,j}$。同时我们将$dp(i,?)$看成一个列向量，于是可以发现$dp(i,?)=Adp(i-1,?)$，从而$dp(n,?)=A^ndp(0,?)$。

这里顺带一提，一般这样做的时间复杂度为$O(m^3\log_2n)$，但是利用BM算法，可以优化到$O(m^3+m^2\log_2n)$。

还有一种优化，就是我们需要求$dp(i_1,?),dp(i_2,?),\ldots,dp(i_k,?)$。一般的时间复杂度为$O(km^3\log_2M)$。其中$M=\max(i_1,\ldots,i_k)$。这里如果$k,m\geq 100$的话，就可能过不了了。有一种比较有用的优化，就是我们预先计算出$A^0,A^1,\ldots,A^{\log_2M}$，时间复杂度为$O(m^3\log_2M)$。之后假如我们要求$dp(i,?)$，我们可以用快速幂的方式来求，总共最多$O(\log_2M)$次矩阵和向量的乘法运算，考虑到$m\times m$矩阵和$m\times 1$的向量的乘积的时间复杂度为$O(m^2)$，因此计算一个$dp(i,?)$的时间复杂度就是$O(m^2\log_2M)$，总的时间复杂度为$O((m+k)m^2\log_2M)$。

再看另外一个问题，假设有一个环，环上标记了$n$个点，记为$0,1,\ldots,n-1$。一个人初始站在$0$上，之后他会走$m$步，每一步它都等概率向前和向后走一步，即假设他现在位于$i$，则有相同的几率会移动到$i+1\pmod n$和$i-1\pmod n$。要求计算最后这个人所站在位置的期望值。

我们可以计算概率，之后通过概率求期望。记$dp(i,j)$表示走了$i$步后，最后$j$处的概率。容易发现有$dp(i,?)=Adp(i-1,?)$，其中$A$是$n\times n$的矩阵。时间复杂度为$O(n^3\log_2m)$。利用之前提到的BM优化技术，可以优化到$O(n^3+n^2\log_2m)$。下面给出更加高效的一个算法。

我们可以用多项式来表示$dp(i,?)$，记$f_i(x)=\sum_{j}dp(i,j)x^j$。那么我们可以记另外一个多项式，表示转移关系$g(x)=x^{-1}+x$。这样我们就可以得到$f_i(x)=g(x)f_{i-1}(x)$。由于$x^{n}=x^0$，因此我们可以有$g(x)=x+x^{n-1}$。计算多项式卷积的时间复杂度为$O(n^2)$，比矩阵的乘积$O(n^3)$要快不少。最终的时间复杂度为$O(n^2\log_2m)$。

上面这个方式还有一些比较丧心病狂的优化。比如如果我们用FFT计算卷积，则时间复杂度为$O(n\log_2n\log_2m)$，但是由于我们实际上算的是$g^m(x)$，我们可以通过计算$e^{m\ln g(x)}$得到，算多项式对数和指数的时间复杂度均为$n\log_2n$，因此最终的时间复杂度为$O(n\log_2n)$。

箱子堆叠问题

题目1：给定$n$个箱子，每个箱子都有由长宽高三个属性组成。现在要求我们将箱子堆叠起来，一个箱子可以放到另外一个箱子的上面，当且仅当上面的箱子的长不超过下面箱子的长，而宽也不超过下面箱子的宽。箱子的长宽是可以互换的。问可以堆叠最高的高度为多少。其中$n\leq 10^6$

我们可以将所有箱子长宽中最大的作为长，长宽中最小的作为宽。可以证明如果两个箱子不能堆叠那么，这两个箱子无论怎么交换长宽都依旧是不能堆叠的。之后可以提前按照箱子的长度进行排序，如果长度相同，就按照宽度进行排序。

接下来可以发现排序放在后面的箱子一定放在排序放在前面的箱子的下面。我们可以发现这个问题类似于LIS问题，记$dp(i,j)$表示前$i$个箱子，最底下箱子的宽度为$j$，最多能堆叠的高度。这个公式利用RMQ可以$O(n\log_2n)$求解。

题目2：给定$n$个箱子，每个箱子都有由长宽高三个属性组成。现在要求我们将箱子堆叠起来，一个箱子可以放到另外一个箱子的上面，当且仅当上面的箱子的长不超过下面箱子的长，而宽也不超过下面箱子的宽。箱子的长宽高都是可以互换的。问可以堆叠最高的高度为多少。其中$n\leq 15$

这道题一种方式就是枚举哪个属性作为高，之后问题就转换成题目1了。时间复杂度为$O(3^nn\log_2n)$。

还有一种方法就是，我们发现这道题的难度实际上是来自于无法确认箱子的上下顺序，我们可以用二进制来确定哪些箱子已经被用了，哪些没有，来去除上下顺序带来的影响。具体做法就是记$dp(s,i,j)$为$s$的箱子集合堆叠在了一起，其中第$i$个箱子，以第$j$个属性为高作为顶部的箱子存在下，最大的高度。这样转移只需要枚举其余箱子，以及用哪个属性作为高，转移的时间复杂度为$O(3n)$。总的时间复杂度为$O(3n^22^n)$。

数位DP

数位DP是个比较常见的技术，其一般用于计算在$[L,R]$（$L\geq 0$）中计算每个数在函数$f$下的总和$\sum_{i=L}^Rf(i)$。

比如我们希望统计区间$[L,R]$中有多少数，满足每一位数只能奇数。那么我们可以定义$f(i)$为$1$当且仅当$i$的每一位均为奇数，否则$f(i)=0$。那么我们就可以用数位DP来计算$\sum_{i=L}^Rf(i)$。

下面考虑怎么计算。我们当然可以暴力枚举，时间复杂度为$O(5^{\log_{10}R})=O(R^{\log_{10}5})$，有点大。我们可以定义$dp(i,floor,ceil)$表示处理完后$i+1$位数字，$floor$指示是否受到$L$的约束，$ceil$指示是否受到$R$的约束。可以发现总共有$2^2\log_{10}R$种状态，每种状态只有$10$种转移需要计算，因此总的时间复杂度为$O(40\log_{10}R)$，是相当快的。

题目1：给定一个矩形，矩形的第$i$行第$j$列的元素为$i\oplus j$，（行号和列号均从$0$开始）。要求计算以$(x_1,y_1)$作为左下角，$(x_2,y_2)$作为右上角的矩形中不超过$k$的数的总和。

这个问题也可以通过数位DP解决的。只不过一般数位DP解决的是一维约束条件，但是这里的约束条件是二维的。

我们可以记$dp(i,xFloor,xCeil,yFloor,yCeil,kCeil)$，表示仅考虑后面$i+1$位数，$xFloor$表示是否受到$x_1$的约束，$xCeil$表示是否受到$x_2$的约束，$yFloor$表示是否受到$y_1$的约束，$yCeil$表示是否受到$y_2$的约束，$kCeil$表示是否受到$k$的约束，返回有多少数满足条件，且满足条件的数的总和。

很显然总共有$2^5\log_2M$种状态，每个状态内部只有$4$个转移，因此时间复杂度为$O(2^7\log_2M)$，还是相当快的。

从这个问题也可以发现，数位DP可以很自然地推广到高维空间中去。

提供一道问题。

一些离散状态的DP

众所周知，大部分情况下我们的DP公式的入参都是一些连续的数值，但是有时候我们发现DP公式的参数是离散的情况。比如这个问题：

问题1：要求将$x=1$变成$n$需要的最少费用，你可以支付费用$A$，令$x=2x$，也可以支付费用$B$，令$x=3x$，也可以支付费用$C$，令$x=5x$，也可以支付费用$D$，令$x=x\pm 1$。其中$n\leq 10^{18}$。

这个问题是经典的离散DP的问题，因为我们不可能开这么大的空间来解决这个问题。一般这类问题我们需要用到哈希表（哈希表很适合存储离散的key）和记忆化搜索（只处理有意义的状态）。那么很显然时间复杂度取决于到底拥有多少状态，上面这个问题可以证明状态数不超过$(\log_2n)^3$，是非常快的。

可以发现离散状态的问题的难点往往是估计状态数，而实际上总是会惊讶的发现真实的状态数非常少。

问题2：给定一个长度为$n$的01序列$A$，我们需要计算其所有子集编码后有多少不同的字符串。其中$0,1$分别可以编码为$0,1$，如果$p,q$分别可以编码为$P,Q$，那么$pq$可以编码为$PQ$，且$p\ldots p$（共$k$个,$k>1$）可以编码为$(p)\times k$。如果$X$是$Y$的子集，则意味着$X$中值为$1$的下标集合是$Y$中值为$1$的下标集合的子集。将结果对某个素数取模。其中$1\leq n\leq 100$

容易发现DP公式：

$$f(A)=(A_1+1)f(A_{2,n})+\sum_{i=1}\sum_{j=2}^{ij\leq n}f(A_{1,i}\land \dots \land A_{(j-1)i+1,ji})f(A_{ji+1,n})$$

其中$n$是$A$的长度，且$A$是01序列。可以$f$的参数也是离散化，很难估计，但是实际上它退化的非常快。理论上其状态数可能达到$2^n$，但是可以发现许多状态都是不可达的，实际上它的状态总数不超过$O(n^3)$。因此我们可以直接暴力DP。

对于大部分离散状态的DP，如果其状态数不好统计，我们大可直接暴力DP，之后利用各种剪枝技巧来优化常数，保证通过最大规模的数据。

DP与拓扑序

称一个长度为$2n$的序列$a_1,\ldots,a_{2n}$为NRS（非减序列），当且仅当这个序列满足$\forall 1\leq i<n(a_i+a_{n-i+1}\leq a_{i+1}+a_{n-i})$。给定一个序列$b_1,\ldots,b_m$，求其中最长的NRS子序列的长度$L$，以及存在多少长度为$L$的NRS子序列，这里$a_i\leq 10^9,2\leq n\leq 1000$。

我们先解决怎么计算$L$。记$dp(l,r)$表示以$a_l$和$a_r$作为两端的最长的NRS的长度。很显然$dp(l,r)=\max_{l<x<y<r\land a_l+a_r\leq a_x+a_y} dp(x,y)$。

我们可以对$r-l$从小到大进行排序处理，并枚举$x,y$就可以在$O(n^4)$时间复杂度内解决这个问题。

但是这个时间复杂度还是比较糟糕的，实际上我们可以进一步优化。考虑我们对$dp(i,j)$按照$a_i+a_j$作为第一关键字，$r-l$作为第二关键字进行排序。

将二维数组视作一个二维矩形块，之后每次查询其实都是查的某个矩形区域，而矩形区域的计算我们可以通过泛化的BIT进行处理，查询和插入的时间复杂度都是$O((\log_2n)^2)$，因此总的时间复杂度为$O(n^2(\log_2n)^2)$。

整数和浮点数DP

很多问题在整数情况下是NP的，但是在浮点数情况下是有多项式解法的。比如整数规划和线性规划。有时候在允许浮点数和仅允许整数的情况下拥有相同的解，比如说最大流、费用流问题等，这时候我们可以用用于浮点数的算法去解决仅允许整数的问题。即使无法完全复用，但是浮点数的做法往往可以给整数做法带来很多好处。

题目1：要求找到$n$个整数$a_1,\ldots,a_n$，满足$\sum_{i=1}^ni\cdot a_i=m$，且费用为$\sum_{i=1}^na_i^2$尽可能小。输出$a_1,\ldots,a_n$。其中$1\leq n\leq 10^5, 1\leq m\leq 10^5$

提供一道题目：SRM738 DriveTheCarHard。

很容易想到一个DP，就是$dp(i,j)$表示在选定$a_1,\ldots,a_i$且$\sum_{k=1}^ik\cdot a_k=j$的前提下，$\sum_{k=1}^ia_k^2$的最小值。这个DP的转移的时间复杂度是$O(m^2\ln n)$，是过不了的。

首先可以发现如果费用在$x$的情况下总和的上限为$y$，那么在费用不超过$x$的前提下总和可以达到$0$到$y$之间的所有值。证明方法非常简单，在我们当前总和为$y>1$时，我们可以找到第一个下标$i$，满足$a_{i-1}\lt a_i$（我们可以认为$a_0=0$)。这样的下标是一定存在的。我们让$a_i$减少$1$，同时让$a_{i-1}$增加$1$，可以发现费用是降低的，并且总和恰好减少$1$。

我们可以分两种情况考虑问题。

一种是$n\geq 500$。这种情况下，我们可以证明结果不会超过$500$，因为$200\times 800\geq m$。因此我们可以重新定义$f(i,j)$表示仅考虑$a_n,a_{n-1},\ldots,a_{n-i+1}$，总费用不超过$j$所能达到的最大总和。这时候时间复杂度为$O(500^{2.5})$。

另外一种方案是$n<500$的情况。

我们来看在允许$a_i$是浮点数情况下，答案是多少。可以发现此时$a_i$带来的收益是$i\cdot a_i$，其带来的费用为$a_i^2$，因此平均收益为$\frac{i}{a_i}$。很显然最终每个未知数的平均收益都是相同的（不然减少平均收益较小的投入，并增大平均收益较大的投入，可以得到更好的结果）。因此$a_i=i\cdot a_1$。之后同时收益的总和为$m$，因此$\sum_{i=1}^ni^2\cdot a_1=m$，可以解出$a_1=\frac{m}{\sum_{i=1}^ni^2}$，从而求出$a_i=\frac{i\cdot m}{\sum_{k=1}^nk^2}$。

虽然浮点数的情况和整数的情况有所区别，但是二者所作的最优决策却会相当接近，即在已知$n,m$的前提下，$a_n和a'_n$非常接近，其中$a'_i$是浮点数的时候的最优决策。

记$opt(i,j)$，$opt(i,j)$表示计算$dp(i,j)$时设置的$a_i$值。同时记$opt'(i,j)$在允许浮点数的时候计算$dp(i,j)$时设置的$a_i$值。最终可以发现$\max_{i,j}|opt(i,j)-opt'(i,j)|$不超过某个常数$\alpha$，在这个问题中$\alpha=2$。因此我们可以$O(\alpha nm)$处理出$dp$（$opt(i,j)$仅可能为$opt'(i,j)\pm 2$）。

状压DP和排列

我们可以用状压DP来存储排列信息。比如下面一个问题：

给定一个$n\times m$的矩阵，要求每一行取正好一个数，每一列最多取一个数。且要求取到的数的总和最大。其中$1\leq n\leq 10, 1\leq m\leq 10^4$。

这个就是经典的排列转状压DP问题了。如果我们知道m个数的排列信息，我们可以直接$O(nm)$进行DP即可，但是这里不知道，如果我们暴力枚举所有可能的排列的话，时间复杂度为$O(n!m)$，这会超时。我们可以记$dp(i,s)$表示仅考虑前$i$列，且$s$中的行都被选择过的最大和，这样可以$O(2^nmn)$时间复杂度内解决这个问题。

同样在有的时候简单的状压可以替换掉子集枚举，考虑下面这个问题。

给定承重为$x$的背包若干个，以及$n$件物品，第$i$件物品的重量为$w_i$。问最少需要多少个这样的背包可以将所有物品都打包带走，保证$1\leq w_i\leq x$，且$1\leq n\leq 20$。

如果我们预先让所有物品按照装入的背包ID排序，则一次$O(n)$迭代即可算出结果。但是这里我们不知道最优顺序，我们只能暴力枚举所有的排列，时间复杂度$O(n!n)$。

我们可以直接上状态压缩，记录$dp(s)$表示装走$s$集合中的物品所需的最少背包，但是在做状态转移的时候我们需要用到枚举子集的技术，这样时间复杂度会达到$O(3^n)$，过不了。

用状压还有一个技巧，就是保存最后一次决策的信息。我们记$f(s)$表示装走$s$集合中的物品所需的最少背包，记$g(s)$表示在用最少背包装走$s$集合中的物品的前提下且要让最后使用的背包总重量最小，最后使用背包的重量。下面考虑转移的时候，我们可以枚举最后背包中的任意一件物品，记这件物品为$i$，则$s$的状态一定是从$s-i$转移而来的。因此我们可以枚举$s$中的元素，时间复杂度降低到$O(n2^n)$，快了很多。

提供一道问题。

区间DP

区间DP一般是将整个区间切分成多个子区间求和的技术。

题目1：给定一个长度为$n$的序列，你每次可以删除序列中的一个连续回文子串，删除完成后剩余的元素重新拼接。问最少需要多少次操作可以将整个序列完全删除。$1\leq n\leq 500$

提供一道题目。

套用区间DP的套路，首先我们可以尝试看看区间$[l,r]$两端的元素是否一起删除。如果不是，则区间必定可以拆分为两个子区间单独决策。否则一起删除，则我们可以继续考虑问题$(l,r)$，如果其至少操作了一次。我们可以将最后一次删除的回文和序列的第$l,r$元素合并为一个新的回文一起删除。否则就必须额外花费一次删除操作。

上面的过程可以$O(n^3)$完成。

分治+FFT

题目1：给定一个包含$n$个顶点$m$条边的图。第$i$条边有长度分别为$1,\ldots,T$的走法，长度为$k$的走法又有$c_{i,k}$种走法。接下来要求对于$t=1,\ldots,T$，计算$f(t)$，即从顶点$1$出发回到顶点$1$的路径中，长度为$t$的不同路径数。结果对素数取模。其中$1\leq n,m\leq 10$，且$1\leq T\leq 5\times 10^4$。

很容易想到一个dp，即$dp(i,j)$表示移动到顶点$i$，走过路径长度为$j$的总走法数。这个方法的转移数比较多，达到了$O(nT+mT^2)$。

接下来考虑如何优化这个DP。可以发现这里的转移非常类似一个卷积，但是我们不能直接卷积，因为我们通过$dp(i,j)$卷积得到$dp(i,j+1)$后，$dp(i,j+1)$依旧会产生额外的贡献。所以这样的话时间复杂度会达到$O((n+m)T^2\log_2T)$。

一种简单的思路是通过分块，对于块大小$B$，这样可以做到时间$O(mT\sqrt{T\log_2T})$，以及一个很大的常数。

还有一种比较靠谱的方式，就是用分治，先计算左边，之后用FFT让左边对右边进行贡献，之后计算右边。可以算出时间复杂度为$O(mT(\log_2T)^2)$。

树上卷积式DP

树上DP有非常多都很类似限定长度的卷积操作，不妨设有$n$个顶点，限定的长度为$m$，满足$1\leq m\leq n$。这时候由于每条边都需要执行一次卷积操作，总共的时间复杂度会类似于$O(nm^2)$，或者如果适用FFT加速的话可以达到$O(nm\log_2m)$的时间复杂度。但是实际测试会发现暴力算法跑的非常快，实际上可以证明真实的时间复杂度为$O(nm)$。

举个例子，在树的每个叶子的权值都是一个特殊的一阶多项式，之后每个非叶子结点的权值为所有子结点的卷积。接下来要求输出根结点权值的前$m$项，可以证明暴力计算的时间复杂度为$O(nm)$。

这里给出证明，卷积发生的情况，根据两个多项式的阶数可以分为三种情况：

1. 两个多项式的阶数均不小于$m$。这时候暴力计算的时间复杂度为$O(m^2)$，因为只需要考虑前$m$项。而这样的多项式最多存在$O(n/m)$个，每次合并都会减少一个这样的多项式，因此总的时间复杂度为$O(nm)$。
2. 两个多项式的阶数都小于$m$，这时候可以发现两个点卷积时产生的贡献类似于两个点在lca除相遇，因此任意两个点都只会贡献1，共生成$O(n/m)$个块，每个块的时间复杂度为$O(m^2)$，这样所有这类操作的时间复杂度之和为$O(nm)$。
3. 一个多项式阶数大于等于$m$，另外一个小于$m$。这时候每个较小多项式众的元素最多产生$O(m)$的贡献，却会减少一个处于多项式阶数小于$m$多项式众的元素。因此总的时间复杂度约束至$O(nm)$。

将三种情况之和加起来就得到了总的时间复杂度$O(nm)$。

提供一些练习题：

• https://atcoder.jp/contests/abc235/tasks/abc235_h

参考资料

• Competitive Programmer’s Handbook