第5章动态规划
动态规划(Dynamic Programming，DP)是算法竞赛的必考题型，内容丰富多变1950年，Richard Bellman把多阶段决策过程命名为Dynamic Programming。闫学灿
在网上发布的算法指导视频中提出“闫氏DP分析法”，用画图辅助DP的建模过程，受到网友
的推崇。。本章将全面介绍动态规划的思想、模板、应用场景和优化等内容。
动态规划是地道的“计算思维”，非常适合用计算机实现，可以说是独属于计算机学科的基础理论。与贪心法、分治一样，动态规划是一种解题的思路，而不是一个具体的算法知识点。动态规划是一种需要学习才能获得的思维方法。像贪心法、分治这样的方法，在生活中和其他学科中有很多类似的例子，很容易联想和理解。但是动态规划不同，它是一种生活中没有的抽象计算方法，没有学过的人很难自发产生这种思路。
本章详解竞赛相关的大部分DP知识点，具体如下。
(1) DP的基本概念和编程方法。
(2) 常见的线性DP问题。
(3) 特殊场景的DP应用，包括数位统计DP、状态压缩DP、区间DP、树形DP等。
(4) DP优化，包括一般优化、单调队列优化、斜率优化、四边形不等式优化等。
扫一扫
视频讲解
5.1DP概念和编程方法
动态规划(DP)是一种算法技术，它将大问题分解为更简单的子问题，对整体问题的最优解决方案取决于子问题的最优解决方案。动态规划常用于求解计数问题(求方案数)和最值问题(最大价值、最小花费)等。
本节介绍DP的基础知识，包括DP的特征、DP的编程方法、DP状态的设计和状态方程的推导，以及DP的空间优化滚动数组。
5.1.1DP的概念
DP是求解多阶段决策问题最优化的一种算法思想，它用于解决具有重叠子问题、最优子结构特征的问题。
下面以斐波那契数列为例说明DP的概念。
斐波那契数列是一个递推数列，它的每个数字是前面两个数字的和，如1，1，2，3，5，8…计算第n个斐波那契数，递推公式为
fib(n)=fib(n-1)+fib(n-2)
斐波那契数列的应用场景是走楼梯问题： 一次可以走一个或两个台阶，问走到第n个台阶时，一共有多少种走法？走楼梯问题的数学模型是斐波那契数列。要走到第n级台阶，分为两种情况，一种是从n-1级台阶走一步过来，另一种是从n-2级台阶走两步过来。
用递归编程求斐波那契数列，代码如下。
1int fib (int n){
2if (n == 1 || n == 2)return 1;
3return (fib (n-1) + fib (n-2)); //递归以2的倍数递增
4}
代码中的递归以2的倍数递增，复杂度为O(2n)，非常差。用DP可以优化复杂度。
为了解决总体问题fib(n)，将其分解为两个较小的子问题，即fib(n-1)和fib(n-2)，这就是DP的应用场景。
一些问题具有两个特征： 重叠子问题、最优子结构。用DP可以高效率地处理具有这两个特征的问题。
图5.1fib（5）分解
1. 重叠子问题
首先，子问题是原大问题的小版本，计算步骤完全一样； 其次，计算大问题时，需要多次重复计算小问题。这就是重叠子问题。以斐波那契数列为例，递归计算fib(5)，分解为如图5.1所示的子问题。
其中，fib(3)计算了两次，其实只计算一次就够了。
一个子问题的多次重复计算，耗费了大量时间。用DP处理重叠子问题，每个子问题只计算一次，从而避免了重复计算，这就是DP效率高的原因。具体的做法是首先分析得到最优子结构，然后用递推或带记忆化搜索的递归进行编程，从而实现高效的计算。
DP在获得时间高效率的同时，可能耗费更多的空间，即时间效率高，空间耗费大。滚动数组是优化空间效率的一个办法。
2. 最优子结构
首先，大问题的最优解包含小问题的最优解； 其次，可以通过小问题的最优解推导出大问题的最优解。这就是最优子结构。在斐波那契数列问题中，把数列的计算构造成fib(n)=fib(n-1)+fib(n-2)，即把原来为n的大问题，减小为n-1和n-2的小问题，这是斐波那契数列的最优子结构。
在DP的概念中，还常常提到“无后效性”。简单地说，就是“未来与过去无关”。此概念不太容易理解，下面以走楼梯问题为例进行解释。要走到第n级台阶，有两种方法，一种是从第n-1级台阶走一步过来，另一种是从第n-2级台阶走两步过来。但是，前面是如何走到第n-1级或第n-2级台阶，fib(n-1)和fib(n-2)是如何计算得到的，并不需要知道，只需要它们的计算结果就行了。换句话说，只关心前面的结果，不关心前面的过程，在计算fib(n)时，直接使用fib(n)和fib(n-1)的结果，不需要知道它们的计算过程，这就是无后效性。
无后效性是应用DP的必要条件，因为只有这样，才能降低算法的复杂度，应用DP才有意义。如果不满足无后效性，那么在计算fib(n)时，还需要重新计算fib(n-1)和fib(n-2)，算法并没有优化。
从最优子结构的概念可以看出，它是满足无后效性的。
这里用斐波那契数列举例说明DP的概念，可能过于简单，不足以说明DP的特征。建议读者用后文的“0/1背包”经典问题重新理解DP的特征。
5.1.2DP的两种编程方法
处理DP中的大问题和小问题，有两种思路： 自顶向下(TopDown，先大问题，再小问题)、自底向上(BottomUp，先小问题，再大问题)。
编码实现DP时，自顶向下用带记忆化搜索的递归编码，自底向上用递推编码。两种方法的复杂度是一样的，每个子问题都计算一遍，而且只计算一遍。
1. 自顶向下与记忆化
先考虑大问题，再缩小到小问题，递归很直接地体现了这种思路。为避免递归时重复计算子问题，可以在子问题得到解决时就保存结果，再次需要这个结果时，直接返回保存的结果就可以了。这种存储已经解决的子问题的结果的技术称为记忆化(Memoization这个英文单词没有写错。https://www.diffbt.com/memoizationvstabulation/解释： In computing，memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.)。
以斐波那契数列为例，记忆化代码如下。
1int memoize［N］;//保存结果
2int fib (int n){
3if (n == 1 || n == 2)return 1;
4if(memoize［n］ != 0)return memoize［n］;//直接返回保存的结果，不再递归
5memoize［n］= fib (n - 1) + fib (n - 2); //递归计算结果，并记忆
6return memoize［n］;
7}
在这段代码中，一个斐波那契数列只计算一次，所以总复杂度为O(n)。
2. 自底向上与制表递推
这种方法与递归的自顶向下相反，避免了用递归编程。自底向上的方法先解决子问题，再递推到大问题，通常通过填写多维表格来完成，编码时用若干for循环语句填表，根据表中的结果，逐步计算出大问题的解决方案。
用制表法计算斐波那契数列，维护一张一维表dp［］，记录自底向上的计算结果，更大的数是前面两个数的和，如下所示。
dp［1］dp［2］dp［3］dp［4］dp［5］dp［6］dp［7］dp［8］…
1123581321…
代码如下。
1const int N = 255;
2int dp［N］;
3int fib (int n){
4dp［1］ = dp［2］ =1;
5for (int i=3;i<=n;i++)dp［i］ = dp［i-1］ +dp［i-2］;
6return dp［n］;
7}
代码的复杂度显然也为O(n)。
制表递推编程时，超过4维(dp［］［］［］［］)的表格也是常见的，表格可以用滚动数组优化空间。
对比自顶向下和自底向上这两种方法，自顶向下的优点是能更宏观地把握问题、认识问题的实质； 自底向上的优点是编码更直接。两种编码方法都很常见。
5.1.3DP的设计和实现
本节以0/1背包问题为例，详细解释与DP的设计、编程有关的内容。滚动数组也应是本节的内容，但是因为比较重要，所以后面单独用一节介绍。
背包问题在DP中很常见，其中0/1背包问题是最基础的，其他背包问题都由它衍生出来崔添翼《背包问题九讲》(https://github.com/tianyicui/pack)介绍了一些背包问题。读者可以阅读这篇文章，如果有费解的地方，请对照本章节对各种背包问题的解释。。
0/1背包问题： 给定n种物品和一个背包，第i个物品的体积为ci，价值为wi，背包的总容量为C。把物品装入背包时，第i种物品只有两种选择： 装入背包或不装入背包，称为0/1背包问题。如何选择装入背包的物品，使装入背包中的物品的总价值最大?
设xi表示物品i装入背包的情况： xi=0时，不装入背包； xi=1时，装入背包。定义：
约束条件： ∑ni=1cixi≤C，xi=0，1
目标函数： max∑ni=1wixi
下面给出一道0/1背包的模板题，以此题为例进行基本DP的讲解。
例5.1Bone collector(hdu 2602)
问题描述： 骨头收集者带着体积为C的背包去捡骨头，已知每块骨头的体积和价值，求能装进背包的最大价值。
输入： 第1行输入测试数量； 后面每3行为一个测试，其中第1行输入骨头数量N和背包体积C，第2行输入每块骨头的价值w，第3行输入每块骨头的体积c。
输出： 最大价值。
数据范围： N≤1000,C≤1000。
1. DP状态的设计
引入一个(N+1)×(C+1)的二维数组dp［］［］，称为DP状态，dp［i］［j］表示把前i个物品(从第1个到第i个)装入容量为j的背包中获得的最大价值。可以把每个dp［i］［j］都看作一个背包： 背包容量为j，装1~i这些物品。最后的dp［N］［C］就是问题的答案——把N个物品装进容量C的背包。
2. DP转移方程
用自底向上的方法计算，假设现在递推到dp［i］［j］，分两种情况：
(1) 第i个物品的体积比容量j还大，不能装进容量j的背包。那么直接继承前i-1个物品装进容量j的背包的情况即可,即dp［i］［j］=dp［i-1］［j］。
(2) 第i个物品的体积比容量j小，能装进背包。又可以分为两种情况： 装或不装第i个物品。
① 装第i个物品。从前i-1个物品的情况推广而来，前i-1个物品的价值为dp［i-1］［j］。 第i个物品装进背包后，背包容量减少c［i］，价值增加w［i］，有dp［i］［j］=dp［i-1］［j-c［i］］+w［i］。
② 不装第i个物品，有dp［i］［j］=dp［i-1］［j］。
取两种情况中的最大值，状态转移方程为
dp［i］［j］=max(dp［i-1］［j］，dp［i-1］［j-c［i］］+w［i］)
总结上述分析，0/1背包问题的重叠子问题是dp［i］［j］，最优子结构是dp［i］［j］的状态转移方程。
算法复杂度： 算法需要计算二维矩阵dp［］［］，二维矩阵的大小为O(NC)，每项计算时间为O(1)，总时间复杂度为O(NC)，空间复杂度为O(NC)。
0/1背包问题的简化版： 一般物品具有体积(或重量)和价值两个属性，求满足体积约束条件下的最大价值。如果再简单一点，只有一个体积属性，求能放到背包的最多物品，那么，只要把体积看作价值，求最大体积就好了。状态转移方程变为
dp［i］［j］=max(dp［i-1］［j］，dp［i-1］［j-c［i］］+c［i］)
3. 详解DP的转移过程
初学者可能对上面的描述仍不太清楚，下面用一个例子详细说明。有4个物品，其体积分别为{2，3，6，5}，价值分别为{6，3，5，4}，背包的容量为9。
填写dp［］［］表的过程，按照只装第1个物品，只装前2个物品，只装前3个物品…的顺序，一直到装完，这就是从小问题扩展到大问题的过程。表格横向为j，纵向为i，按先横向递增j，再纵向递增i的顺序填表。dp［］［］矩阵如图5.2所示。
步骤1： 只装第1个物品。
由于物品1的体积为2，所以背包容量小于2的，都放不进去，即dp［1］［0］=dp［1］［1］=0。
若物品1的体积等于背包容量，能放进去，背包价值等于物品1的价值，即dp［1］［2］=6。
容量大于2的背包，多余的容量用不到，所以价值与容量为2的背包一样，如图5.3所示。
图5.2dp［］［］矩阵
图5.3装第1个物品
步骤2： 只装前2个物品。
如果物品2体积比背包容量大，那么不能装物品2，情况与只装第1个物品一样。dp［2］［0］=dp［2］［1］=0，dp［2］［2］=6。
下面填写dp［2］［3］。物品2体积等于背包容量，那么可以装物品2，也可以不装。
如果装物品2(体积为3，价值也为3)，那么可以变成一个更小的问题，即只把物品1装到容量为j-3的背包中，如图5.4所示。
如果不装物品2，那么相当于只把物品1装到背包中，如图5.5所示。
图5.4装第2个物品
图5.5不装第2个物品
取两种情况的最大值，得dp［2］［3］=max{3,6}=6。
后续步骤： 继续以上过程，最后得到如图5.6所示的dp矩阵(图中的箭头是几个例子)。
最后的答案是dp［4］［9］，把4个物品装到容量为9的背包，最大价值为11。
4. 输出背包方案
现在回头看具体装了哪些物品。需要倒过来观察：
dp［4］［9］=max{dp［3］［4］+4，dp［3］［9］}=dp［3］［9］，说明没有装物品4，用x4=0表示；
dp［3］［9］=max{dp［2］［3］+5，dp［2］［9］}=dp［2］［3］+5=11，说明装了物品3，x3=1；
dp［2］［3］=max{dp［1］［0］+3，dp［1］［3］}=dp［1］［3］，说明没有装物品2，x2=0；
dp［1］［3］=max{dp［0］［1］+6，dp［0］［3］}=dp［0］［1］+6=6，说明装了物品1，x1=1。
如图5.7所示，实线箭头标识了方案的转移路径。
图5.6完成dp矩阵
图5.7背包方案
5. 递推代码和记忆化代码
下面的代码分别用自底向上的递推和自顶向下的记忆化递归实现。
1) 递推代码
1#include<bits/stdc++.h>
2using namespace std;
3const int N = 1011;
4int w［N］, c［N］;// 物品的价值和体积
5int dp［N］［N］;
6int solve(int n, int C){
7for(int i=1; i<=n; i++)
8for(int j=0; j<=C; j++){
9if(c［i］ > j)dp［i］［j］ = dp［i-1］［j］;//第i个物品比背包还大，装不了
10elsedp［i］［j］ = max(dp［i-1］［j］,dp［i-1］［j-c［i］］+w［i］);//第i个物品能装
11}
12return dp［n］［C］;
13}
14int main(){
15int T; cin>>T;
16while(T--){
17int n,C; cin >> n >> C;
18for(int i=1;i<=n;i++) cin>>w［i］;
19for(int i=1;i<=n;i++) cin>>c［i］;
20memset(dp,0,sizeof(dp)); //清零，置初值为0
21cout << solve(n, C) << endl;
22}
23return 0;
24}
2) 记忆化代码
记忆化代码只改动递推代码中的solve()函数。
1int solve(int i, int j){//前i个物品，放进容量j的背包
2if (dp［i］［j］ != 0) return dp［i］［j］; //记忆化
3if(i == 0) return 0;
4int res;
5if(c［i］ > j) res =solve(i-1,j); //第i个物品比背包还大，装不了
6elseres = max(solve(i-1,j), solve(i-1,j-c［i］)+w［i］); //第i个物品可以装
7return dp［i］［j］ = res;
8}
本节的0/1背包问题，物品价值都大于0，且背包容量有最大限制。在6.6节“0/1分数规划”给出的例题Talent show G（洛谷 P4377)中，物品的价值可以为负数，且背包容量有最小限制，请思考这种背包问题并参考第6章的代码。
5.1.4滚动数组
滚动数组是DP最常使用的空间优化技术。
DP的状态方程常常是二维和二维以上，占用了太多空间。例如，5.1.3节的代码使用了二维矩阵int dp［N］［C］，设N=103，C=104，都不算大，但int型占据4B，矩阵需要的空间为4×103×104≈40MB，已经超过一般竞赛题的空间限制。
用滚动数组可以大大减少空间。它能把二维状态方程O(n2)的空间复杂度优化到一维的O(n)，更高维的数组也可以优化后减少一维。
从状态转移方程dp［i］［j］=max(dp［i-1］［j］，dp［i-1］［j-c［i］］+w［i］)可以看出，dp［i］［］只与dp［i-1］［］有关，和前面的dp［i-2］［］，dp［i-3］［］，…都没有关系。从前面的图表也可以看出，每行是通过上面一行算出来的，与更前面的行没有关系。那些用过的已经无用的dp［i-2］［］，dp［i-3］［］，…多余了，那么干脆就复用这些空间，用新的一行覆盖已经无用的一行(滚动)，只需要两行就够了。
下面给出滚动数组的两种实现方法“交替滚动”和“自我滚动”是本书提出的名词。，两种实现方法都很常用。
1. 交替滚动
定义dp［2］［j］，用dp［0］［］和dp［1］［］交替滚动。这种方法的优点是逻辑清晰，编码不易出错，建议初学者采用这种方法。
下面的代码中，now始终指向正在计算的最新的一行，old指向已计算过的旧的一行。对照原递推代码，now相当于i，old相当于i-1。
1// hdu 2602(滚动数组代码1)
2int dp［2］［N］; //替换 int dp［］［］;
3int solve(int n, int C){
4int now = 0, old = 1; //now指向当前正在计算的一行，old指向旧的一行
5for(int i=1; i<=n; i++){
6swap(old,now);//交替滚动，now始终指向最新的一行
7for(int j = 0; j <= C; j++){
8 if(c［i］ > j)dp［now］［j］ = dp［old］［j］;
9 else dp［now］［j］ = max(dp［old］［j］, dp［old］［j-c［i］］+w［i］);
10}
11}
12return dp［now］［C］;//返回最新的行
13}
注意，j循环是0~C，其实反过来也可以。但是在下面的“自我滚动”代码中，必须反过来循环，即C~0。
2. 自我滚动
用两行做交替滚动在逻辑上很清晰，但是还能继续精简： 一维dp［］就够了，自己滚动自己。
1// hdu 2602(滚动数组代码2)
2int dp［N］;
3int solve(int n, int C){
4for(int i=1; i<=n; i++)
5for(int j=C; j>=c［i］; j--) //反过来循环
6dp［j］ = max(dp［j］,dp［j-c［i］］+w［i］);
7return dp［C］;
8}
注意，j应该反过来循环，即从后向前覆盖。下面说明原因，用dp［j］′表示旧状态，dp［j］表示滚动后的新状态。
(1) j从小到大循环是错误的。例如，i=2时，图5.8左侧的dp［5］，经计算得到dp［5］=9，把dp［5］更新为9。继续计算，当计算dp［8］时，得dp［8］=dp［5］′+3=9+3=12，这个答案是错的。错误的产生是由动数组重复使用同一个空间引起的。
图5.8j从小到大循环，是错误的
(2) j从大到小循环是对的。例如，i=2时，首先计算最后的dp［9］=9，它不影响前面状态的计算，如图5.9所示。
图5.9j从大到小循环，是正确的
经过交替滚动或自我滚动的优化，DP的空间复杂度从O(N×C)降低到O(C)。
滚动数组也有缺点。它覆盖了中间转移状态，只留下了最后的状态，所以损失了很多信息，导致无法输出具体的方案。
二维以上的dp数组也能优化。例如，求dp［t］［］［］，如果它只和dp［t-1］［］［］有关，不需要dp［t-2］［］［］、dp［t-3］［］［］等，那么可以把数组缩小为dp［2］［］［］或dp［］［］。
扫一扫
视频讲解
5.2经典线性DP问题
本节介绍一些经典DP问题，这些问题比较简单，常常出现在面试中更多动态规划问题可参考https://www.geeksforgeeks.org/dynamicprogramming/。。请大量练习这种题目，熟练掌握DP的算法思想。
1. 分组背包
有一些物品，把物品分为n组，其中第i组第k个物品的体积为c［i］［k］，价值为w［i］［k］； 每组内的物品冲突，每组内最多只能选出一个物品装进背包； 给定一个容量为C的背包，问如何选物品，使装进背包的物品的总价值最大。
解题思路与0/1背包问题很相似。回顾0/1背包问题的状态定义dp［i］［j］，它表示把前i个物品(第1~i个)装入容量为j的背包中获得的最大价值。
类似地，在分组背包中定义状态dp［i］［j］，它表示把前i组物品装进容量j的背包(每组最多选一个物品)可获得的最大价值。状态转移方程为
dp［i］［j］=max{dp［i-1］［j］，dp［i-1］［j-c［i］［k］］+w［i］［k］}
其中，dp［i-1］［j］表示第i组不选物品； dp［i-1］［j-c［i］［k］］表示第i组选第k个物品。求解方程，需要做i、j、k的三重循环。
如果用滚动数组实现，状态转移方程变为
dp［j］=max{dp［j］，dp［j-c［i］［k］］+w［i］［k］}
下面是一道简单例题，用来演示代码。
例5.2ACboy needs your help(hdu 1712)
问题描述： ACboy这学期可以选N门课，他只想学M天。每门课的学分不同，问这M天如何安排N门课，才能得到最多学分？
输入： 有多个测试。每个测试的第1行输入N和M。后面有N行，每行输入M个数字，表示一个矩阵A［i］［j］，1≤i≤N≤100，1≤j≤M≤100，表示第i门课学j天能得到A［i］［j］学分。若N=M=0，表示测试结束。
输出： 对每个测试，输出最多学分。
以第1个测试为例，N=M=2，第1门课学1天得1分，学2天得2分； 第2门课学1天得1分，学2天得3分； ACboy的选择是用2天学第2门课。本题可以建模为分组背包，每门课是一组。
物品分组： 第i门课是第i组，天数是物品的体积，A［i］［j］是第j个物品的价值。
背包容量： 总天数M就是背包容量。
下面是用滚动数组实现的代码，注意它是“自我滚动”，所以j是从大到小循环的。
1#include<bits/stdc++.h>
2using namespace std;
3const int N=105;
4int w［N］［N］,c［N］［N］; //物品的价值、体积
5int dp［N］;
6int n,m;
7int main(){
8while(scanf("%d%d",&n,&m) && n && m){ //输入： n门课，即n组； m天，即容量为m
9for(int i=1;i<=n;i++) //第i门课，即第i组
10for(int k=1;k<=m;k++){//m也是第i组的物品个数
11scanf("%d",&w［i］［k］); //第i组第k个物品的价值
12c［i］［k］ = k;//第i组第k个物品的体积，学k天才能得分，体积就是k
13}
14memset(dp,0,sizeof(dp));
15for(int i=1;i<=n;i++) //n门课，即n组； 遍历每门课，即遍历每个组
16for(int j=m;j>=0;j--) //容量为m
17for(int k=1;k<=m;k++) //用k遍历第i组的所有物品
18if(j >= c［i］［k］)//第k个物品能装进容量j的背包
19 dp［j］ = max(dp［j］, dp［j-c［i］［k］］ + w［i］［k］); //第i组第k个
20printf("%d＼n",dp［m］);
21}
22}
2. 多重背包
给定n种物品和一个背包，第i种物品的体积为ci，价值为wi，并且有mi个，背包的总容量为C。如何选择装入背包的物品，使装入背包中物品的总价值最大?
例5.3宝物筛选(洛谷 P1776)
输入： 第1行输入整数n和C，分别表示物品种数和背包的最大容量。
接下来n行中，每行输入3个整数wi、ci、mi，分别表示第i个物品的价值、体积、数量。
输出： 输出一个整数，表示背包不超载的情况下装入物品的最大价值。
下面给出3种解法。
1) 简单方法
下面给出两种思路。
第1种思路是转换为0/1背包问题。把相同的mi个第i种物品看作独立的mi个物品，共有∑ni=1mi个物品，然后按0/1背包问题求解，复杂度为OC∑ni=1mi。
第2种思路是直接求解。定义状态dp［i］［j］表示把前i个物品装进容量j的背包，能装进背包的最大价值。第i个物品分为装或不装两种情况，得到多重背包的状态转移方程为
dp［i］［j］=max{dp［i-1］［j］，dp［i-1］［j-k·c［i］］+k·w［i］}，
1≤k≤min{m［i］，j/c［i］}
直接写i、j、k三重循环，复杂度与第1种思路一样。下面用滚动数组编码，提交判题后会超时。
1//洛谷 P1776： 滚动数组版本的多重背包(超时)
2#include <bits/stdc++.h>
3using namespace std;
4const int N=100010;
5int n,C,dp［N］;
6int w［N］,c［N］,m［N］;//物品i的价值、体积、数量
7int main(){
8cin >> n >> C; //物品数量，背包容量
9for(int i=1;i<=n;i++) cin>>w［i］>>c［i］>>m［i］;
10//以下是滚动数组版本的多重背包
11for(int i=1;i<=n;i++)//枚举物品
12for(int j=C;j>=c［i］;j--) //枚举背包容量
13for(int k=1; k<=m［i］ && k*c［i］<=j; k++)
14dp［j］ = max(dp［j］,dp［j-k*c［i］］+k*w［i］);
15cout << dp［C］ << endl;
16return 0;
17}
2) 二进制拆分优化
这是一种简单而有效的技巧。在上述简单方法的基础上加入这个优化，能显著改善复杂度。原理很简单，例如，第i种物品有mi=25个，这25个物品放进背包的组合有0~25的26种情况。不过，要组合成26种情况，其实并不需要25个物品。根据二进制的计算原理，任何一个十进制整数X都可以用1，2，4，8等2的倍数相加得到，如25=16+8+1，这些2的倍数只有log2X个。题目中第i种物品有mi个，用log2mi个数就能组合出0~mi种情况。总复杂度从OC∑ni=1mi优化到OC∑ni=1log2mi。
注意拆分的具体实现，不能全部拆成2的倍数，而是先按2的倍数从小到大拆，最后是一个小于或等于最大倍数的余数。对mi这样拆分非常有必要，能够保证拆出的数相加在［1，mi］范围内，不会大于mi。例如，mi=25，把它拆成1+2+4+8+10，最后是余数10，10<16=24，读者可以验证用这5个数能组合成1~25的所有数字，不会超过25。
1//洛谷 P1776： 二进制拆分+滚动数组
2#include <bits/stdc++.h>
3using namespace std;
4const int N=100010;
5int n,C,dp［N］;
6int w［N］,c［N］,m［N］;
7int new_n; //二进制拆分后的新物品总数量
8int new_w［N］,new_c［N］,new_m［N］;//二进制拆分后的新物品
9int main(){
10cin >> n >>C;
11for(int i=1;i<=n;i++)cin>>w［i］>>c［i］>>m［i］;
12//以下是二进制拆分
13int new_n = 0;
14for(int i=1;i<=n;i++){
15for(int j=1;j<=m［i］;j<<=1) { //二进制枚举： 1,2,4，...
16m［i］-=j; //减去已拆分的
17new_c［++new_n］ = j*c［i］; //新物品
18new_w［new_n］ = j*w［i］;
19}
20if(m［i］){//最后一个是余数
21new_c［++new_n］ = m［i］*c［i］;
22new_w［new_n］ = m［i］*w［i］;
23}
24}
25//以下是滚动数组版本的0/1背包
26for(int i=1;i<=new_n;i++)//枚举物品
27for(int j=C;j>=new_c［i］;j--) //枚举背包容量
28dp［j］ = max(dp［j］,dp［j-new_c［i］］+new_w［i］);
29cout << dp［C］ << endl;
30return 0;
31}
这种解法可以看作多重背包问题的标准解法，不过，还有更优的解法——单调队列优化。
3) 单调队列优化
这种方法的复杂度为O(nC)，是最优的解法。详情见5.8节。
洛谷P2347“砝码称重”是一道类似的多重背包问题，请读者练习用二进制拆分优化解决。
3. 最长公共子序列(Longest Common Subsequence，LCS)
一个给定序列的子序列，是在该序列中删去若干元素后得到的序列。例如，X={A，B，C，B，D，A，B}，它的子序列有{A，B，C，B，A}、{A，B，D}、{B，C，D，B}等。子序列和子串是不同的概念，子串的元素在原序列中是连续的。
给定两个序列X和Y，当另一序列Z既是X的子序列，又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列是长度最长的公共子序列。
问题描述： 给定两个序列X和Y，找出X和Y的一个最长公共子序列。
用暴力法找最长公共子序列，需要先找出X的所有子序列，然后一一验证是否为Y的子序列。如果X有m个元素，那么X有2m个子序列； Y有n个元素； 总复杂度大于O(n2m)。
用动态规划求LCS，复杂度为O(nm)。用dp［i］［j］表示序列Xi(表示x1,x2,…，xi这个序列，即X的前i个元素组成的序列； 这里用小写的x表示元素，用大写的X表示序列)和Yj(表示y1,y2,…，yj这个序列，即Y的前j个元素组成的序列)的最长公共子序列的长度。dp［n］［m］就是答案。
分解为以下两种情况。
(1) 当xi=yj时，已求得Xi-1和Yj-1的最长公共子序列，在其尾部加上xi 或yj，即可得到Xi和Yj的最长公共子序列。状态转移方程为dp［i］［j］=dp［i-1］［j-1］+1。
(2) 当xi≠ yj时，求解两个子问题： Xi-1和Yj的最长公共子序列、Xi和Yj-1的最长公共子序列。取其中的最大值，状态转移方程为dp［i］［j］=max{dp［i］［j-1］，dp［i-1］［j］}。
习题： hdu 1159(Common subsequence)。
4. 最长递增子序列(Longest Increasing Subsequence，LIS)
问题描述： 给定一个长度为n的数组，找出一个最长的单调递增子序列。
例如，一个长度为7的序列A={5，6，7，4，2，8，3}，它最长的单调递增子序列为{5，6，7，8}，长度为4。
定义状态dp［i］表示以第i个数为结尾的最长递增子序列的长度，那么有
dp［i］=max{dp［j］}+1,0<j<i,Aj<Ai
最终答案是max{dp［i］}。
复杂度分析： j在0~i滑动，复杂度为O(n)； i的变化范围也为O(n)； 总复杂度为O(n2)。
DP并不是LIS问题的最优解法，有复杂度为O(nlog2n)的非DP解法参考《算法竞赛入门到进阶》7.1.4节“最长递增子序列”的详细讲解。。
习题： hdu 1257(最少拦截系统)。
5. 编辑距离(Edit Distance)
问题描述： 给定两个单词word1和word2，计算出将word1转换为word2所需的最小操作数。一个单词允许进行3种操作： ①插入一个字符； ②删除一个字符； ③替换一个字符。
为方便理解，把长度为m的word1存储在数组word1［1］~word1［m］，把长度为n的word2存储在数组word2［1］~word2［n］，不使用word1［0］和word2［0］。
图5.10编辑距离的dp
转换矩阵
定义二维数组 dp，dp［i］［j］表示从 word1 的前i个字符转换到word2的前j个字符所需要的操作步骤，dp［m］［n］就是答案。图5.10所示为word1="abcf"，word2="bcfe"的dp转移矩阵。
若word1［i］=word2［j］，则dp［i］［j］=dp［i-1］［j-1］，如图5.10中dp［2］［1］处的箭头所示。
其他情况，dp［i］［j］=min{dp［i-1］［j-1］，dp［i-1］［j］，dp［i］［j-1］}+1,如图5.10中dp［4］［2］处的箭头所示。dp［i］［j］是它左侧、左上、上方的3个值中的最小值加1，分别对应以下3种操作：
(1) dp［i-1］［j］+1，删除，将word1的最后字符删除；
(2) dp［i］［j-1］+1，插入，在word2的最后插入word1的最后字符；
(3) dp［i-1］［j-1］+1，替换，将word2的最后一个字符替换为word1的最后一个字符。
算法复杂度为O(mn)。
习题： 洛谷P2758。
6. 最小划分(Minimum Partition)
问题描述： 给出一个正整数数组，把它分成S1和S2两部分，使S1的数字和与S2的数字和的差的绝对值最小。最小划分的特例是S1和S2的数字和相等，即差为0。
例如，数组［1，6，11，5］，最小划分是S1=［1，5，6］，S2=［11］； S1的数字和减去S2的数字和，绝对值为|11-12|=1。
最小划分问题可以转化为0/1背包问题。求出数组的和sum，把问题转换为： 背包的容量为sum/2，把数组中的每个数字看作物品的体积，求出背包最多可以放res体积的物品，返回结果|res-(sum-res)|。
习题： lintcode 724(Minimum partition)https://www.lintcode.com/problem/minimumpartition/description。
7. 行走问题(Ways to Cover a Distance)
问题描述： 给定一个整数n，表示距离的步骤，一个人每次能走1~3步，问要走到n，有多少种走法？例如，n=3，有4种走法： {1，1，1}、{1，2}、{2，1}、{3}。
这个问题和爬楼梯问题差不多。爬楼梯问题是每次能走1级或2级台阶，问走到第n级有多少种走法。爬楼梯问题的解实际上是一个斐波那契数列。
定义行走问题的状态dp［i］为走到第i步的走法数量，那么有
dp［0］=1，dp［1］=1，dp［2］=2
dp［i］=dp［i-1］+dp［i-2］+dp［i-3］，i>2
8. 矩阵最长递增路径(Longest Path in Matrix)
问题描述： 给定一个矩阵，找一条最长路径，要求路径上的数字递增。矩阵的每个点可以向上、下、左、右4个方向移动，不能沿对角线方向移动。
例如，矩阵993
757
311的一个最长递增路径为1379，长度为4。
下面给出两种解法。
(1) 暴力DFS。设矩阵有m×n个点，以每个点为起点做DFS，搜索递增路径，在所有递增路径中找出最长的路径。每个DFS都是指数级时间复杂度的，复杂度非常高。
(2) 记忆化搜索。在暴力DFS的基础上，用记忆化进行优化。把每个点用DFS得到的最长递增路径记下来，后面再搜索到这个点时，直接返回结果。由于每个点只计算一次，每条边也只计算一次，虽然做了m×n次DFS，但是总复杂度仍然为O(V+E)=O(mn)，其中V为点数，E为边数。这也算是动态规划的方法。
习题： leetcode 329(矩阵中的最长递增路径)https://leetcodecn.com/problems/longestincreasingpathinamatrix/。
9.子集和问题(Subset Sum Problem)
问题描述： 给定一个非负整数的集合S，一个值M，问S中是否有一个子集，其子集和等于M。
例如，S={6，2，9，8，3，7}，M=5，存在一个子集{2，3}，子集和等于5。
用暴力法求解，即检查所有的子集。共有2n个子集，为什么？用二进制辅助理解： 若一个元素被选中，标记为1； 若没有选中，标记为0； 空集是n个0，所有元素都被选中是n个1，从n个0到n个1，共有2n个。
用DP求解，定义二维数组dp。当dp［i］［j］=1时，表示S的前i个元素存在一个子集和等于j。问题的答案就是dp［n］［M］。
用S［1］～S［n］记录集合S的n个元素。
分析状态转移方程，分为两种情况。
(1) 若S［i］>j，则S［i］不能放在子集中，有dp［i］［j］=dp［i-1］［j］。
(2) 若S［i］≤j，有两种选择： 不把S［i］放在子集中，则dp［i］［j］=dp［i-1］［j］； 把S［i］放在子集中，则dp［i］［j］=dp［i-1］［j-S［i］］。
这两种情况，只要其中一个为1，那么dp［i］［j］就为1。
图5.11子集和问题的dp矩阵
读者可以用图5.11的例子进行验证。
如果已经确定问题有解，即dp［n］［M］=1，如何输出子集内的元素？按推导状态转移方程的思路，从dp［n］［M］开始，沿着dp矩阵倒推回去即可。
10. 最优游戏策略(Optimal Strategy for a Game)
问题描述问题和样例来自https://www.geeksforgeeks.org/optimalstrategyforagamedp31/。： 有n堆硬币排成一行，它们的价值分别是v1，v2，…，vn，n为偶数； 两人交替拿硬币，每次只能在剩下的硬币中拿走第1堆或最后一堆。如果你是先手，你能拿到的最大价值是多少？
例如，v={8，15，3，7}，先手这样拿可以获胜： 先手拿7； 对手拿8； 先手再拿15； 对手再拿3，结束。先手拿到的最大价值为7+15=22。
本题不能用贪心法。例如，在样例中，如果先手第1次拿8，那么对手接下来肯定拿15，先手失败。
定义二维数组dp，dp［i］［j］表示从第i堆到第j堆硬币区间内，先手能拿到的最大值。
在硬币区间［i，j］，先手有以下两个选择。
(1) 拿i。接着对手也有两个选择： 拿i+1，剩下［i+2，j］； 或拿j，剩下［i+1，j-1］。在这两个选择中，对手必然选择对先手不利的拿法。
(2) 拿j。接着对手也有两个选择： 拿i，剩下［i+1，j-1］； 拿j-1，剩下［i，j-2］。
得到dp转移方程还有一种DP方案，参考https://www.geeksforgeeks.org/optimalstrategyforagameset2/。如下。
dp［i］［j］=max{V［i］+min(dp［i+2］［j］，dp［i+1］［j-1］)，
V［j］+min(dp［i+1］［j-1］，dp［i］［j-2］)}
dp［i］［j］=V［i］，j=i
dp［i］［j］=max(V［i］，V［j］)，j=i+1
11. 矩阵链乘法(Matrix Chain Multiplication)
先了解背景知识。
(1) 矩阵乘法。如果矩阵A和B能相乘，那么A的列数等于B的行数。设A为m行n列(记为m×n)，B为n×u，那么乘积AB的尺寸为m×u，矩阵乘法AB需要做m×n×u次乘法运算。
(2) 矩阵乘法的结合律： (AB)C=A(BC)。括号体现了计算的先后顺序。
(3) 括号位置不同，矩阵乘法需要的乘法操作次数不同。以矩阵A、B、C的乘法为例，设A的尺寸为m×n，B的尺寸为n×u，C的尺寸为u×v，以下两种计算方法，需要的乘法次数分别为
(AB)C，乘法次数是 m×n×u+m×u×v
A(BC)，乘法次数是 m×n×v+n×u×v
两者的差是|m×n×(u-v)+u×v×(m-n)|，它可能是一个巨大的值。如果能知道哪个括号方案是最优的，就能够大大减少计算量。
下面给出矩阵链乘法问题的定义： 给定一个数组p［］，其中p［i-1］×p［i］表示矩阵Ai的尺寸，输出最少的乘法次数，并输出此时的括号方案。
例如，p［］={40，20，30，10，30}，它表示4个矩阵，尺寸分别为40×20，20×30，30×10，10×30。4个矩阵相乘，当括号方案为(A(BC))D时，有最少乘法次数(26000)。
如果读者学过区间DP，就会发现这是一个典型的区间DP问题。设链乘的矩阵为AiAi+1…Aj，即区间［i，j］，那么按结合率，可以把它分成两个子区间［i，k］和［k+1，j］，分别链乘，有
AiAi+1…Aj=(Ai…Ak)(Ak+1…Aj)
必定有一个k，使乘法次数最少，记这个k为ki,j。并且记Ai,j为此时AiAi+1…Aj通过加括号后得到的一个最优方案，它被ki,j分开。
那么子链AiAi+1…Ak的方案Ai,k、子链Ak+1Ak+2…Aj的方案Ak+1,j也都是最优括号子方案。
这样就形成了递推关系，即
Ai,j=min{Ai,k+Ak+1,j+pi-1pkpj}
用二维矩阵dp［i］［j］表示Ai,j，得到转移方程为
dp［i］［j］=
0，i=j
min{dp［i］［k］+dp［k+1］［j］+pi-1pkpj}，i≤k<j
dp［1］［n］就是答案，即最少乘法次数。
dp［i］［j］的编码实现，可以套用区间DP模板，遍历i、j、k，复杂度为O(n3)。
区间DP常常可以用四边形不等式优化，但是本题不可以，因为它不符合四边形不等式优化所需要的单调性条件。
习题： poj 1651(Multiplication puzzle)。
12. 布尔括号问题(Boolean Parenthesization Problem)
问题描述https://www.geeksforgeeks.org/booleanparenthesizationproblemdp37/： 布尔变量有两种取值： T(true)和F(false)。定义3种布尔逻辑操作： &(与)、|(或)、^(异或)。现在输入： n个取值符号，n-1个逻辑操作。加上括号可以改变执行顺序。要使结果是T，共有多少种括号方案？
输入样例： symbol［］={T，F，T}，operator［］={^，&}
输出样例： 2
提示： 两种方案为((T ^ F) & T)和(T ^(F & T))。
13. 最短公共超序列(Shortest Common Supersequence)
问题描述https://www.geeksforgeeks.org/shortestcommonsupersequence/： 给定两个字符串str1和str2，找一个最短的字符串，使str1和str2是它的子序列。
例如，str1="AGGTAB",str2="GXTXAYB"，输出"AGXGTXAYB"。
【习题】
(1) 洛谷P1216/P1020/P1091/P1095/P1541/P1868/P2679/P2501/P3336/P3558/P4158/P5301。
(2) poj 1015/3176/1163/1080/1159/1837/1276/1014。
扫一扫
视频讲解
5.3数位统计DP
数位统计DP用于数字的数位统计，是一种比较简单的DP套路题。
一个数字的数位有个位、十位、百位，等等，如果题目和数位统计有关，那么可以用DP思想，把低位的统计结果记录下来，在高位计算时直接使用低位的结果，从而提高效率。
用下面一道例题详解数位统计DP的建模和两种实现： 递推、记忆化搜索。
数位统计有关的题目，基本内容是处理“前导0”和“数位限制”。
例5.4数字计数(洛谷P2602，poj 2282)
问题描述： 给定两个正整数a和b，求在［a，b］的所有整数中，每个数码(digit)各出现了多少次。
输入： 输入两个整数a和b。
输出： 输出10个整数，分别表示0~9在［a，b］中出现了多少次。
数据范围： 1≤a≤b≤1012。
首先转换一下题目的要求。区间［a，b］等于［1，a-1］与［1，b］的差分，把问题转换为在区间［1，x］内，统计数字0~9各出现了多少次。
由于a和b的值太大，用暴力法直接统计［a，b］内的每个整数显然会超时，需要设计一个复杂度约为O(log2n)的算法。如何加快统计？容易想到DP——把对低位数的统计结果用于高位数的统计。例如，统计出三位数之后，继续统计一个四位数时，对这个四位数的后3位的统计直接引用前面的结果。以统计［0，324］内数位2出现了多少次为例，搜索过程如图5.12所示。其中，下画线的数字区间是前面已经计算过的，记录在状态dp［］中，不用再重算； 符号*表示区间中有数位2，需要特殊处理。
图5.12统计［0，324］内数位2出现的次数
把［0，324］区间分解为4个区间： 000~099、100~199、200~299、300~324。其中，000~099、100~199、200~299能够沿用00~99的计算结果。至于300~324，最高位3不是要找的数位2，等价于计算00~24。
称数字前面的0为“前导0”，如000~099中的0。称每位的数字为“数位限制”，如324中最高位的3、次高位的2、最低位的4。计数统计时需要特判前导0和数位限制，后面有详细解释。
下面分别用递推和记忆化搜索两种编码方法实现。
5.3.1数位统计DP的递推实现
定义状态dp［］，dp［i］为i位数的每种数字有多少个，说明如下。
(1) 一位数0~9，每种数字有dp［1］=1个。
(2) 二位数00~99，每种数字有dp［2］=20个。注意，这里是00~99，不是0~99。如果是0~99，0只出现了11次。这里把0和其他数字一样看待，但编程时需要特殊处理，因为按照习惯写法，数字前面的0应该去掉，如043应该写成43。前导0在0~9、00~99、000~999等所有情况下都需要特殊处理。
(3) 三位数000~999，每种数字有dp［3］=300个。
(4) 四位数0000~9999，每种数字有dp［4］=4000个，依此类推。
dp［］有两种计算方法。
(1) dp［i］=dp［i-1］×10+10i-1，
这是从递推的角度分析得到的。以数字2为例，计算dp［2］时，2在个位上出现了dp［i-1］×10=dp［1］×10=10次，即2，12，22，…，92； 在十位上出现了10i-1=102-1=10次，即20，21，22，…，29。计算dp［3］时，2在个位和十位上出现了dp［2］×10=200次，在百位上出现了103-1=100次。
(2) dp［i］=i×10i/10，
这是按排列组合的思路得到的。因为从i个0递增到i个9，所有的字符共出现了i×10i次，0~9每个数字出现了i×10i/10次。
下面考虑如何编程。以［0，324］为例，先从324的最高位开始，每种数字的出现次数cnt计算如下。
(1) 普通情况。例如，00~99共出现了3次，分别出现在000~099、100~199、200~299的后两位上，每个数字在后两位上共出现dp［i-1］×num［i］=dp［2］×3=60次。对应代码第23行。
(2) 特判当前的最高位，即“数位限制”。第3位上的数字有0、1、2、3，3是最高位的数位限制。数字0、1、2分别在000~099、100~199、200~299的最高位上出现了100次，对应代码第24行； 数字3在300~324中出现了25次，对应代码第25~27行。
(3) 特判前导0。在前面的计算中，都把0和其他数字一样看待，但前导0应该去掉。对应代码第28行。
1//改写自https://www.luogu.com.cn/blog/mak2333/solution-p2602
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5const int N=15;
6ll ten［N］,dp［N］;
7ll cnta［N］,cntb［N］; //cnt［i］，统计数字i出现了多少次
8int num［N］;
9void init(){//预计算dp［］
10ten［0］ = 1; //ten［i］: 10的i次方
11for(int i=1;i<=N;i++){
12dp［i］= i*ten［i-1］;//或者写成dp［i］= dp［i-1］*10+ten［i-1］;
13ten［i］ = 10*ten［i-1］;
14}
15}
16void solve(ll x, ll *cnt){
17int len = 0; //数字x有多少位
18while(x){ //分解x，num［i］为x的第i位数字
19num［++len］ = x%10;
20x=x/10;
21}
22for(int i=len;i>=1;i--){//从高到低处理x的每位
23for(int j=0;j<=9;j++)cnt［j］ += dp［i-1］*num［i］;
24for(int j=0;j<num［i］;j++)cnt［j］ += ten［i-1］; //特判最高位比num［i］小的数字
25ll num2 = 0;
26for(int j=i-1;j>=1;j--)num2 = num2*10+num［j］;
27cnt［num［i］］ += num2+1;//特判最高位的数字num［i］
28cnt［0］ -= ten［i-1］; //特判前导0
29}
30}
31int main(){
32init();
33ll a,b;cin >> a>>b;
34solve(a-1, cnta), solve(b, cntb);
35for(int i=0;i<=9;i++)cout << cntb［i］-cnta［i］ <<" ";
36}
分析代码的复杂度，solve()函数有两层for循环，只循环了10×len次。
5.3.2数位统计DP的记忆化搜索实现
回顾记忆化搜索，其思路是在递归函数dfs()中搜索所有可能的情况，遇到已经计算过的记录在dp中的结果，就直接使用，不再重复计算。
用递归函数dfs()实现上述记忆化搜索，执行过程如下。如图5.12所示，以［0，324］为例，从输入324开始，一直递归到最深处的(0)，然后逐步回退，图中用箭头上的数字标识了回退的顺序。
记忆化搜索极大地减少了搜索次数。例如，统计000~099中2的个数，因为用dp［］进行记忆化搜索，计算5次即可； 如果去掉记忆化部分，需要检查每个数字，共100次。
下面设计dp状态。和前面递推的编码类似，记忆化搜索的代码中也需要处理前导0和每位的最高位。编码时，每次统计0~9中的一个数字，代码中用变量now表示这个数字。下面的解释都以now=2为例。
定义状态dp［］［］，用来记录0~9、00~99、000~999这样的无数位限制情况下2的个数，以及20~29、200~299、220~229、2200~2299这种前面带有2的情况下2的个数。
dp［pos］［sum］表示最后pos位范围是［0…0pos个，99…9pos个］，前面2的个数为sum时，数字2的总个数。例如，dp［1］［0］=1表示00~09，10~19，30~39，…区间内2的个数为1；
dp［1］［1］=11表示20~29区间内2的个数为11；
dp［1］［2］=21表示220~229区间内2的个数为21；
dp［1］［3］=31表示2220~2229区间内2的个数为31；
dp［2］［0］=20表示000~099，100~199，300~399，400~499，…区间内2的个数为20；
dp［2］［1］=120表示200~299区间内2的个数为120；
dp［2］［2］=220表示2200~2299区间内2的个数为220； 等等。
用lead标识是否有前导0，lead=false表示没有前导0，lead=true表示有前导0。
用limit标识当前最高位的情况，即“数位限制”的情况。如果是0~9，limit=false； 否则limit=true。例如［0，324］，计算324的最高位时，范围是0~3，此时limit=true。再如，从最高位数字1递归到下一位时，下一位的范围是0~9，此时limit=false。如果不太理解，请对比前面递推实现的解释。
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4const int N = 15;
5ll dp［N］［N］;
6int num［N］,now; //now： 当前统计0~9的哪一个数字
7ll dfs(int pos,int sum,bool lead, bool limit){//pos： 当前处理到第pos位
8ll ans = 0;
9if(pos == 0) return sum;//递归到0位数，结束，返回
10if(!lead && !limit && dp［pos］［sum］!=-1)return dp［pos］［sum］; //记忆化搜索
11int up = (limit ? num［pos］ : 9);//这一位的最大值，如324的第3位是up = 3
12for(int i=0;i<=up;i++){ //下面以now=2为例
13if(i==0 && lead)ans += dfs(pos -1, sum,true, limit&&i==up);
14//计算000~099
15else if(i == now) ans += dfs(pos -1, sum+1,false,limit&&i==up);
16//计算200~299
17else if(i != now) ans += dfs(pos -1, sum,false,limit&&i==up);
18//计算100~199
19}
20if(!lead && !limit) dp［pos］［sum］ = ans; //状态记录： 无前导0
21return ans;
22}
23ll solve(ll x){
24int len = 0; //数字x有多少位
25while(x){
26num［++len］ = x%10;
27x/=10;
28}
29memset(dp,-1,sizeof(dp));
30return dfs(len,0,true,true);
31}
32int main(){
33ll a,b;cin>>a>>b;
34for(int i=0;i<10;i++) now = i, cout << solve(b)-solve(a-1)<<" ";
35return 0;
36}
代码中的dp［pos］［sum］，有队员习惯把limit和lead也加进去，定义为dp［pos］［sum］［lead］［limit］。
具体实现见下面的代码。
1//用下面的代码替换上面的部分代码。只有3行不同
2ll dp［N］［N］［2］［2］;//这一行不同
3ll dfs(int pos, int sum, bool lead, bool limit){
4ll ans = 0;
5if (pos == 0) return sum;
6if (dp［pos］［sum］［limit］［lead］ != -1) return dp［pos］［sum］［limit］［lead］; //这一行不同
7int up = (limit ? num［pos］ : 9);
8for(int i=0;i<=up;i++){
9if(i==0 && lead)ans += dfs(pos -1, sum,true, limit&&i==up);
10else if(i == now) ans += dfs(pos -1, sum+1,false,limit&&i==up);
11else if(i != now) ans += dfs(pos -1, sum,false,limit&&i==up);
12}
13dp［pos］［sum］［limit］［lead］ = ans;//这一行不同
14return ans;
15}
记忆化搜索代码的复杂度和递推代码一样。
本题是数位统计DP的套路题，记忆化搜索的代码可以当作模板，下面的几道题套用了模板，关键是处理前导0和数位限制。
5.3.3数位统计DP例题
下面用两道例题巩固对数位统计DP的理解。
1. 洛谷P2657
例5.5Windy数(洛谷P2657)
问题描述： 不含前导0且相邻两位数字之差至少为2的正整数称为Windy数。问在a和b之间(包括a和b)，总共有多少个Windy数？(特例： 把一位数0~9看成Windy数)
输入： 输入两个整数a和b，1≤a≤b≤2×109。
输出： 输出一个整数，表示答案。
输入样例：
25 50输出样例：
20
在输入样例［25，50］区间中，32、33、34、43、44、45不是Windy数，如数字32，3-2=1<2。
求区间［a，b］内的Windy数，可以转换为分别求［1，a-1］和［1，b］区间。问题转换为给定一个数x，求［0，x］内有多少个Windy数。
这是一道明显的数位统计DP题。检查一个很大的数时，对高位部分的检查可以沿用低位部分的检查结果。例如，计算0~342的Windy数，分为统计000~099、100~199、200~299、300~342内的Windy数。这与前面的洛谷P2602模板题的思路一样。
定义状态dp［pos］［last］，表示数字长度为pos位，前一位是last的情况下(包括前导0)的无数位限制的Windy数总数。
例如，dp［1］［0］=8表示00~09区间内Windy数有8个，数字长度pos=1，前一位last=1。注意此时前导0也是合法的，其中00和01不是Windy数，02~09是Windy数，共8个。如果不算前导0，0~9内应该有10个Windy数。
dp［1］［1］=7表示10~19区间内Windy数有7个；
dp［1］［2］=7表示20~29区间内Windy数有7个；
dp［2］［0］=57表示000~099区间内Windy数有57个，此时前导0也是合法的，如果不算前导0，0~99区间内应该有74个Windy数；
dp［2］［1］=50表示100~199区间内Windy数有50个；
dp［2］［2］=51表示200~299区间内Windy数有51个；
dp［2］［3］=51表示300~399区间内Windy数有51个；
dp［3］［1］=362表示1000~1999区间内Windy数有362个。
本题的代码与洛谷P2602模板题相似。其中，lead和limit变量的含义也相同，分别标识前导0和数位限制。
1#include<bits/stdc++.h>
2using namespace std;
3int dp［15］［15］, num［15］;
4int dfs(int pos, int last, bool lead, bool limit){
5int ans = 0;
6if(pos == 0) return 1;
7if(!lead && !limit && dp［pos］［last］!=-1) return dp［pos］［last］;
8int up = (limit?num［pos］:9);
9for(int i=0;i<=up;i++){
10if(abs(i-last)<2)continue; //不是Windy数
11if(lead && i==0) ans += dfs(pos-1,-2,true, limit&&i==up);
12else ans += dfs(pos-1,i,false, limit&&i==up);
13}
14if(!limit && !lead) dp［pos］［last］ = ans;
15return ans;
16}
17int solve(int x){
18int len = 0;
19while(x) { num［++len］=x%10; x/=10;}
20memset(dp,-1,sizeof(dp));
21return dfs(len,-2,true,true);
22}
23int main(){
24int a,b; cin >>a>>b;
25cout << solve(b)-solve(a-1);
26return 0;
27}
2. 洛谷P4124
例5.6手机号码(洛谷P4124)
问题描述： 选手机号码，号码必须同时包含两个特征： 手机号码中至少要出现3个相邻的相同数字； 号码中不能同时出现8和4。例如，满足条件的号码有13000988721、23333333333、14444101000； 而不满足条件的号码有1015400080、10010012022。手机号码一定是11 位数，不含前导0。给出两个数a和b，统计出［a，b］区间内所有满足条件的号码数量。a和b也是11 位的手机号码。
输入： 两个整数a和b，1010≤a≤b≤1011。
输出： 输出一个整数表示答案。
输入样例：
12121284000 12121285550输出样例样例解释： 满足条件的号码有12121285000、 12121285111、 12121285222、 12121285333、 12121285550。：
5
本题也是数位统计DP的套路题。
本题可以回避前导0。因为号码是11位的，最高位为1~9，只要限定最高位不为0即可。
定义状态dp［pos］［u］［v］［state］［n8］［n4］，其中pos表示当前数字长度，u表示前一位数字，v表示再前一位数字，state标识是否出现3个连续相同数字，n8标识是否出现8，n4标识是否出现4。
其他代码和前面模板题相似。
1//改写自www.luogu.com.cn/blog/yushuotong-std/solution--4124
2#include<bits/stdc++.h>
3using namespace std;
4typedef long long ll;
5ll dp［15］［11］［11］［2］［2］［2］;
6int num［15］;
7ll dfs(int pos,int u,int v,bool state,bool n8,bool n4,bool limit){
8ll ans=0;
9 if(n8 && n4) return 0;//8和4不能同时出现
10 if(!pos) return state;
11 if(!limit && dp［pos］［u］［v］［state］［n8］［n4］!=-1) return dp［pos］［u］［v］［state］［n8］［n4］;
12 int up = (limit?num［pos］:9);
13 for(int i=0;i<=up;i++)
14ans += dfs(pos-1,i,u,state||(i==u&&i==v),n8||(i==8),n4||(i==4),
limit&&(i==up));
15 if(!limit)dp［pos］［u］［v］［state］［n8］［n4］=ans;
16 return ans;
17}
18ll solve(ll x){
19 int len = 0;
20 while(x){num［++len］=x%10; x/=10;}
21 if(len!=11) return 0;
22 memset(&dp,-1,sizeof(dp));
23 ll ans = 0;
24 for(int i=1;i<=num［len］;i++)//最高位1~9，避开前导0问题
25ans+= dfs(len-1,i,0,0,i==8,i==4,i==num［len］);
26 return ans;
27}
28int main(){
29 ll a,b;cin >> a>>b;
30 cout <<solve(b)-solve(a-1);
31}
【习题】
(1) 洛谷 P4798/P3281/P2518/P3286/P4999。
(2) poj 3252。
扫一扫
视频讲解
5.4状态压缩DP
状态压缩是DP“状态压缩DP、区间DP、树形DP”这些名词可能是中国算法竞赛选手创造的，英文可以翻译为： DP on Subsets(状态压缩DP)； DP over Intervals(区间DP)； DP on Trees(树形DP)。的一个小技巧，一般应用在集合问题中。当DP状态是集合时，把集合的组合或排列用一个二进制数表示，这个二进制数的0/1组合表示集合的一个子集，从而把对DP状态的处理转换为二进制的位操作，让代码变得简洁易写，同时提高算法效率。从二进制操作简化集合处理的角度看，状态压缩也是一种DP优化方法。
5.4.1引子
1. Hamilton问题
状态压缩DP常常用Hamilton(旅行商)问题作为引子。
例5.7最短Hamilton路径https://www.acwing.com/problem/content/description/93/
问题描述： 给定一个有权无向图，包括n个点，标记为0~n-1，以及连接n个点的边，求从起点0到终点n-1的最短路径。要求必须经过所有点，而且只经过一次。1≤n≤20。
输入： 第1行输入整数n。接下来n行中，每行输入n个整数，其中第i行第j个整数表示点i到j的距离，记为a［i，j］。0≤a［i，j］≤107。
对于任意x，y，z，数据保证 a［x，x］=0，a［x，y］=a［y，x］且 a［x，y］+a［y，z］≥a［x，z］。
输出： 输出一个整数，表示最短Hamilton路径的长度。
时间限制： 3s。
Hamilton问题是NP问题，没有多项式复杂度的解法。
先尝试暴力解法，枚举n个点的全排列。共有n!个全排列，一个全排列就是一条路径，计算每个全排列的路径长度，需要做n次加法。在所有路径中找最短的路径，总复杂度为O(n×n!)。
2. DP求解Hamilton问题
如果用状态压缩DP求解，能把复杂度降低到O(n2×2n)。当n=20时，O(n2×2n)≈4亿，比暴力法好很多。下面介绍状态压缩DP的做法。
首先定义dp状态。设S为图的一个子集，用dp［S］［j］表示集合S内的最短Hamilton路径，即从起点0出发经过S中的所有点，到达终点j时的最短路径(集合S中包括j点)。然后根据DP的思路，让S从最小的子集逐步扩展到整个图，最后得到的dp［N］［n-1］就是答案，N表示包含图上所有点的集合。
如何求dp［S］［j］？可以从小问题S-j递推到大问题S。其中，S-j表示从集合S中去掉j，即不包含j点的集合。
如何从S-j递推到S？设k为S-j中的一个点，把
0~j的路径分为两部分： 01…k和k(k+1)…j。以k为变量枚举S-j中所有点，找出最短的路径，状态转移方程为
dp［S］［j］=min{dp［S-j］［k］+dist(k，j)}，k ∈ S-j
图5.13枚举集合S-j中所有点
集合S初始时只包含起点0，然后逐步将图中的点包含进来，直到最后包含所有点。这个过程用状态转移方程实现。
用图5.13可解释上述原理。读者可以体会为什么用DP遍历路径比用暴力法遍历路径更有效率。其关键在于已经遍历过的点的顺序对以后的决策没有影响，这体现了DP的无后效性。
3. 用状态压缩DP编码
以上是dp状态设计，接下来是编程实现，最重要的是如何操作集合S。这就是状态压缩DP的技巧： 用一个二进制数表示集合S，把S“压缩”到一个二进制数中。这个二进制数的每位表示图上的一个点，等于0表示S不包含这个点，等于1表示包含。例如，S=0011 0101，其中有4个1，表示集合中包含5、4、2、0共4个点。本题最多有20个点，那么就定义一个20位的二进制数表示集合S。
下面给出代码，第1个for循环有2n次，加上后面两个各n次的for循环，总复杂度为O(n2×2n)。
第1个for循环实现了从最小的集合扩展到整个集合。最小的集合为S=1，它的二进制数只有最后一位是1，即包含起点0； 最大的集合是S=(1<<n)-1，它的二进制数中有n个1，包含了所有点。
算法最关键的部分是“枚举集合S-j中所有点”，是通过代码中的两个if语句实现的：
if((S>>j) & 1)，判断当前的集合S中是否含有j点；
if((S^(1<<j))>>k & 1)，其中S^(1<<j)的作用是从集合中去掉
j点，得到集合S-j，然后>> k & 1表示用k遍历集合中的1，这些1就是S-j中的点，这样就实现了“枚举集合S-j中所有的点”。注意，S^(1<<j)也可以写为S-(1<<j)。
这两个语句可以写在一起： if(((S>>j) & 1) &&((S^(1<<j))>>k & 1))，不过分开写效率更高。
1#include <bits/stdc++.h>
2using namespace std;
3int n, dp［1<<20］［21］;
4int dist［21］［21］;
5int main(){
6memset(dp,0x3f,sizeof(dp));//初始化最大值
7cin>>n;
8for(int i=0; i<n; i++) //输入图
9for(int j=0; j<n; j++)
10cin >> dist［i］［j］; //输入点之间的距离
11dp［1］［0］=0;//开始： 集合中只有点0，起点和终点都是0
12for(int S=1; S<(1<<n); S++)//从小集合扩展到大集合，集合用S的二进制表示
13for(int j=0; j<n; j++) //枚举点j
14if((S>>j) & 1) //(1)这个判断与下面的(2)同时起作用
15for(int k=0; k<n; k++)//枚举到达j的点k，k属于集合S-j
16if((S^(1<<j)) >> k & 1) //(2)k属于集合S-j，S-j用(1)保证
17//把(1)和(2)写在一起，更容易理解，但是效率低一点
18//if( ((S>>j) & 1) && ((S^(1<<j)) >> k & 1) )
19 dp［S］［j］ = min(dp［S］［j］,dp［S^(1<<j)］［k］ + dist［k］［j］);
20cout << dp［(1<<n)-1］［n-1］; //输出： 路径包含了所有的点，终点是n-1
21return 0;
22}
上述Hamilton问题指定了起点和终点，类似的题目有洛谷 P1433。这一题略有不同，它指定了起点0，但是没有指定终点，把上面的代码略加修改即可。在上面的代码中，最后求得dp［(1<<n)-1］［j］，表示起点为0，终点为j，经过所有点的最短路径。查询所有dp［(1<<n)-1］［j］中的最小值，就是洛谷 P1433的答案。
5.4.2状态压缩DP的原理
从5.4.1节可知，状态压缩DP的应用背景是以集合为状态，且集合一般用二进制表示，用二进制的位运算处理，所以又可以称为“集合DP所以，一般把状态压缩DP翻译为DP on Subsets，即“子集上的DP”。”。
集合问题一般是指数复杂度的(NP问题)，例如： ①子集问题，设n个元素无先后关系，那么共有2n个子集； ②排列问题，对所有n个元素进行全排列，共有n!个全排列。
可以这样概况状态压缩DP的思想： 如果用二进制表示集合的状态(子集或排列)，并用二进制的位运算遍历和操作，又简单又快。当然，由于集合问题是NP问题，所以状态压缩DP的复杂度仍然是指数级的，只能用于小规模问题的求解。
一个问题能用状态压缩DP求解，时间复杂度主要取决于DP算法，与是否使用状态压缩关系不大。状态压缩只是DP处理集合的工具，也可以用其他工具处理集合，只是不太方便，时间复杂度也差一点。
C语言的位运算符有&、|、^、<<、>>等，下面给出一些例子。虽然数字是用十进制表示的，但位运算是按二进制处理的。
1#include<bits/stdc++.h>
2int main(){
3int a = 213, b = 21; // a = 1101 0101, b = 0001 1001
4printf("a & b = %d＼n",a & b);// AND=17, 二进制0001 0001
5printf("a | b = %d＼n",a | b);// OR = 221, 二进制1101 1101
6printf("a ^ b = %d＼n",a ^ b);// XOR= 204, 二进制1100 1100
7printf("a << 2 = %d＼n",a << 2);// a*4= 852, 二进制0011 0101 0100
8printf("a >> 2 = %d＼n",a >> 2);// a/4=53, 二进制0011 0101
9int i = 5; //a的第i位是否为1
10if((1 << (i-1)) & a)printf("a［%d］=%d＼n",i,1); //a的第i位是1
11elseprintf("a［%d］=%d＼n",i,0); //a的第i位是0
12a = 43, i = 5; //把a的第i位改成1，a = 0010 1011
13printf("a=%d＼n",a | (1<<(i-1))); //a=59, 二进制0011 1011
14a = 242; //把a最后的1去掉，a = 1111 0010
15printf("a=%d＼n", a & (a-1)); //去掉最后的1，a=240, 二进制1111 0000
16return 0;
17}
用位运算可以简便地对集合进行操作，表5.1给出了几个操作，在上面的代码中已有演示。
表5.1用位运算对集合进行操作
说明操作
判断a的第i位(从最低位开始数)是否等于11 <<(i-1)) & a
把a的第i位改成1a |(1<<(i-1))
把a的第i位改成0a &(~(1<<i))
把a的最后一个1去掉a &(a-1)
在具体题目中需要灵活使用位运算。后面的例题给出了位运算操作集合的实际应用的例子，帮助读者更好地掌握。
5.4.3状态压缩DP例题
1. poj 2411
本题是状态压缩DP的经典例题，其特点是“轮廓线在“插头DP”中大量使用了轮廓线的概念。”。
例5.8Mondriaan’s dream(poj 2411)
问题描述： 给定n行m列的矩形，用1×2的砖块填充，有多少种填充方案？
例如，n×m=2×4时，有5种方案； n×m=2×3时，有3种方案，如图5.14所示。
图5.14填充方案案例
输入： 每行是一个测试用例，输入两个整数n和m。若n=m=0，表示终止。1≤n，m≤11。
输出： 对每个测试用例，输出方案数。
摆放砖块的操作步骤，可以从第1行第1列开始，从左向右、从上向下依次摆放。横砖只占一行，不影响下一行的摆放； 竖砖占两行，会影响下一行。同一行内，前列的摆放决定后列的摆放。例如，第1列放横砖，那么第2列就是横砖的后半部分； 第1列放竖砖，那么就不影响第2列。上、下两行是相关的，如果上一行是横砖，则不影响下一行； 如果上一行是竖砖，那么下一行的同一列是竖砖的后半部分。
读者可以先对比暴力搜索的方法。使用BFS，从第1行第1列开始扩展到全局，每个格子的砖块有横放、竖放2种摆法，共m×n个格子，复杂度大约为O(2m×n)。
下面用DP求解。DP的思想是从小问题扩展到大问题，本题中，是否能从第1行开始，逐步扩展，直到最后一行？本题的复杂性在于一个砖块可能影响连续的两行，而不是一行，必须考虑连续两行的情况。
如图5.15所示，用一条虚线把矩形分为两部分，上半部分已经填充完毕，下半部分未完成。把这条划分矩形的虚线称为轮廓线。
图5.15用轮廓线划分矩形
轮廓线下面的6个阴影方格k5k4k3k2k1k0表示当前的砖块状态，它跨越了两行。从它们推广到下一个方格x，即递推到新状态k4k3k2k1k0x。
k5k4k3k2k1k0有各种情况，用0表示没有填充砖块，用1表示填充了砖块，共有000000~111111共26种情况。图5.15(b)是一个例子，其中k3未填充，k5k4k3k2k1k0=110111。用二进制表示状态，这就是状态压缩的技术。
注意，根据DP递推的操作步骤，递推到阴影方格时，砖块只能填充到阴影格本身和上面的部分，不能填到下面。在图5.15(c)中，把k2填充到下面是错误的。
这26种情况中有些是非法的，应该去掉。在扩展到x时，分析26种情况和x的对应关系，根据x是否填充砖块，有3种情况。
(1) x=0(x不放砖块)。如果k5=0(k5上没有砖块)，由于k5只剩下和x一起填充的机会，现在失去了这一机会，所以这个情况是非法的； 如果k5=1，则x=0可以成立，递推到k4k3k2k1k0x=k4k3k2k1k00。
(2) x=1(x放竖砖)。x只能和k5一起放竖砖，要求k5=0，递推到k4k3k2k1k0x=k4k3k2k1k01。
(3) x=1(x放横砖)。x只能和k0一起放横转，要求k0=0，另外还应有k5=1，递推到k4k3k2k1k0x=k4k3k2k111。
经过上述讨论，对n×m的矩阵，可以得到状态定义和状态转移方程。
1) 状态定义
定义DP状态为dp［i］［j］［k］，它表示递推到第i行第j列，且轮廓线处填充为k时的方案总数。
其中，k是用m位二进制表示的连续m个方格，这m个方格中的最后一个方格就是第i行第j列的方格。k中的0表示方格不填充，1表示填充。m个方格前面的所有方格(轮廓线以上的部分)都已经填充为1。dp［n-1］［m-1］［(1<<m) -1］就是答案，它表示递推到最后一行，最后一列，k的二进制是m个1(表示最后一行全填充)。
时间复杂度为O(m×n×2m)。
后面给出的代码用到了滚动数组，把二维［i］［j］改为一维，状态定义变为dp［2］［k］。
2) 状态转移
根据前面分析的3种情况，分别转移到新的状态。
(1) x=0，k5=1。从k=k5k4k3k2k1k0=1k4k3k2k1k0转移到k=k4k3k2k1k00。转移代码为
dp［now］［(k<<1) &(~(1<<m))］+=dp［old］［k］;
其中，~(1<<m)表示原来的k5=1移到了第m+1位，超出了k的范围，需要把它置0。
(2) x=1，k5=0。从k=k5k4k3k2k1k0=0k4k3k2k1k0转移到k=k4k3k2k1k01。转移代码为
dp［now］［(k<<1)^1］+=dp［old］［k］;
(3) x=1，k0=0，k5=1。从k=k5k4k3k2k1k0=k5k4k3k2k11转移到k=k4k3k2k111。转移代码为
dp［now］［((k<<1) | 3) &(~(1<<m))］+=dp［old］［k］;
其中，(k<<1)|3表示末尾置11； ~(1<<m)表示原来的k5=1移到了第m+1位，把它置0。
下面是poj 2411的代码。
1#include <iostream>
2#include <cstring>
3using namespace std;
4long long dp［2］［1<<11］;
5int now,old;//滚动数组，now指向新的一行，old指向旧的一行
6int main(){
7int n,m;
8while( cin>>n>>m && n ){
9if(m>n) swap(n,m);//复杂度为O(nm*2^m), m较小有利
10memset(dp,0,sizeof(dp));
11now=0,old=1;//滚动数组
12dp［now］［(1<<m)-1］=1;
13for(int i=0;i<n;i++)//n行
14for(int j=0;j<m;j++){ //m列
15swap(now,old);//滚动数组，now始终指向最新的一行
16memset(dp［now］,0,sizeof(dp［now］));
17for(int k=0;k<(1<<m);k++){//k为轮廓线上的m格
18if(k & 1<<(m-1))//情况(1)： 要求k5=1
19 dp［now］［(k<<1) & (~(1<<m))］ += dp［old］［k］;
20 //原来的k5=1移到了第m+1位，置0
21if(i && !(k & 1<<(m-1) ) ) //情况(2)
22 //i不等于0，即i不是第1行，另外要求k5=0
23 dp［now］［(k<<1)^1］ += dp［old］［k］;
24if(j && (!(k&1)) && (k & 1<<(m-1)) ) //情况(3)
25 //j不等于0，即j不是第1列，另外要求k0=0, k5=1
26 dp［now］［((k<<1) | 3) & (~(1<<m))］ += dp［old］［k］;
27 //k末尾置为11，且原来的k5移到了第m+1位，置0
28}
29}
30cout << dp［now］［(1<<m)-1］<<endl;
31}
32return 0;
33}
2. hdu 4539
例5.9排兵布阵(hdu 4539)
问题描述： 团长带兵来到n×m的平原作战。每个士兵可以攻击到并且只能攻击到与其曼哈顿距离为2的位置以及士兵本身所在的位置。当然，一个士兵不能站在另外一个士兵所能攻击到的位置； 同时，因为地形，平原上也不是每个位置都可以安排士兵。现在，已知n、m(n≤100，m≤10)以及平原阵地的具体地形，请你帮助团长计算该阵地最多能安排多少士兵。
输入： 包含多组测试数据。每组测试的第1行输入两个整数n和m； 接下来的n行中，每行输入m个数，表示n×m的矩形阵地，其中1表示该位置可以安排士兵，0表示该地形不允许安排士兵。
输出： 对每组测试，输出最多能安排的士兵数量。
输入样例：
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0输出样例：
2
图5.16的例子是一个合理的安排，图中的1表示一个站立的士兵，×表示曼哈顿距离为2的攻击点，不能安排其他士兵。
图5.16士兵和他的攻击点
本题的思路比较容易。
首先考虑暴力法。对一种站立安排，如果任意两个士兵都没有站在曼哈顿距离为2的位置上，就是一个合法的安排。但是一共有2n×m种站立安排，显然不能用暴力法判断。
下面考虑DP的思路。从第1行开始，一行一行地放士兵，在每行都判断合法性，直到最后一行。假设递推到了第i行，只需要看它和第i-1、i-2行的情况即可。
(1) 判断第i行自身的合法性。这一行站立的士兵，不能站在曼哈顿距离为2的位置上。例如，m=6时，合法的士兵站立情况有000010、000011、0000110、100011、110011等。
(2) 判断第i行和第i-1行的合法性。第i行任何一个士兵与第i-1行士兵的曼哈顿距离不能为2。
(3) 判断第i行和第i-2行的合法性。
(4) 判断第i-1行和第i-2行的合法性。
定义DP状态dp［i］［j］［k］表示递推到第i行时的最多士兵安排数量，此时第i行的士兵站立情况为j，第i-1行的士兵站立情况为k。在j和k的二进制表示中，0表示有士兵，1表示无士兵。
从第i-1行递推到第i行，状态转移方程为
dp［i］［j］［k］=max(dp［i-1］［k］［p］)+count_line(i，sta［j］)
其中，count_line(i,sta［j］)计算第i行在合法的j状态下的士兵数量; 用p遍历第i-2行的合法情况。
下面给出代码。代码中有4个for循环，复杂度为O(nM3)。M是预计算出的一行的合法情况数量，当m=10时，M=169。用init_line()函数预计算一行的合法情况。
1//代码改写自https://blog.csdn.net/jzmzy/article/details/20950205
2#include <bits/stdc++.h>
3using namespace std;
4int mp［105］［12］;//地图
5int dp［105］［200］［200］;
6int n,m;
7int sta［200］;//预计算一行的合法情况，m = 10时只有169种合法情况
8int init_line(int n){//预计算出一行的合法情况
9int M = 0;
10for(int i = 0; i < n; i ++)
11if((i&(i>>2))==0 && (i&(i<<2))==0)//左右间隔2的位置没人，就是合法的
12 sta［M++］ = i;
13return M;//返回合法情况有多少种
14}
15int count_line(int i, int x){//计算第i行的士兵数量
16int sum = 0;
17for(int j=m-1; j>=0; j--) {//x是预计算过的合法安排
18if(x&1) sum += mp［i］［j］; //把x与地形匹配
19x >>= 1;
20}
21return sum;
22}
23int main(){
24while(~scanf("%d%d",&n,&m)) {
25int M = init_line(1<<m);//预计算一行的合法情况，有M种
26for(int i = 0; i < n; i ++)
27for(int j = 0; j < m; j ++)
28scanf("%d",&mp［i］［j］);//输入地图
29int ans = 0;
30memset(dp, 0, sizeof(dp));
31for(int i = 0; i < n; i ++) //第i行
32for(int j = 0; j < M; j ++) //枚举第i行的合法安排
33for(int k = 0; k < M; k ++) {
//枚举第i-1行的合法安排
34if(i == 0) {//计算第1行
35dp［i］［j］［k］ = count_line(i, sta［j］);
36ans = max(ans, dp［i］［j］［k］);
37continue;
38}
39if((sta［j］&(sta［k］>>1)) || (sta［j］&(sta［k］<<1)))
40continue; //第i行和第i-1行冲突
41int tmp = 0;
42for(int p = 0; p < M; p ++){ //枚举第i-2行合法状态
43if((sta［p］&(sta［k］>>1)) || (sta［p］&(sta［k］<<1))) continue;
44 //第i-1行和第i-2行冲突
45if(sta［j］&sta［p］) continue;//第i行和第i-2行冲突
46tmp = max(tmp, dp［i-1］［k］［p］); //从第i-1行递推到第i行
47}
48dp［i］［j］［k］ = tmp + count_line(i, sta［j］);
49 //加上第i行的士兵数量
50ans = max(ans, dp［i］［j］［k］);
51}
52printf("%d＼n",ans);
53}
54return 0;
55}
5.4.4三进制状态压缩DP
前面的状态压缩DP都利用了二进制运算，除了用二进制做状态压缩，也可以用其他进制，如三进制。用下面的例题说明三进制状态压缩DP。
例5.10hdu 3001
问题描述： Acmer先生决定访问n座城市。他可以空降到任意城市，然后开始访问，要求访问到所有城市，任何一座城市访问的次数不少于一次，不多于两次。n座城市间有m条道路，每条道路都有路费。求Acmer先生完成旅行需要花费的最小费用。
输入： 第1行输入n和m，1≤n≤10。后面m行中，输入3个整数a、b、c，表示城市a和b之间的路费为c。
输出： 最少花费，如果不能完成旅行，则输出-1。
本题中n≤10，数据很小，但是由于每座城市可以走两遍，可能的路线就有(2n)!条，所以不能用暴力法。
本题是旅行商问题的变形，编程方法和Hamilton路径问题非常相似。阅读下面的题解时，请与5.4.1节的解释对照。
在普通路径问题中，一座城市只有两种情况： 访问和不访问，分别用1和0表示，可以用二进制进行状态压缩。但是本题有3种情况： 不访问、访问一次、访问两次，所以用三进制进行状态压缩分别用0、1、2表示。
当n=10时，路径有310条，每种路径用三进制表示。例如，第14条路径，十进制14的三进制为1123，它的意思是： 第3座城市走一次，第2座城市走一次，第1座城市走两次。
用tri［i］［j］定义路径，它表示第i条路径上的城市j的状态。在上面的例子中，
tri［14］［3］=1，tri［14］
图5.17枚举路径i-j中所有点
［2］=1，tri［14］［1］=2。make_trb()函数完成初始化计算，它把十进制14转换为三进制1123，并赋值给tri［i］［j］。
定义DP状态dp［j］［i］表示从城市j出发，按路径i访问i中所有城市的最小费用。
枚举路径i-j中所有点，如图5.17所示。
图5.17中，i-j表示从路径i中去掉城市j。从城市j开始访问路径i，等于先走完路径i-j，再走到城市j。用k遍历i-j中的所有城市，找到最少费用，状态转移方程为
dp［j］［i］=min(dp［j］［i］，dp［k］［l］+graph［k］［j］)
其中，l=i-bit［j］，它涉及本题的关键操作： 从路径i中去掉城市j。这是三进制状态压缩的关键问题，如何从集合中去掉某个元素？
回顾5.4.1节的二进制状态压缩，是这样从集合S中去掉点j的： S^(1<<j)，它等价于S-(1<<j)。类似地，在三进制中，从i中去掉j的代码写为i-bit［j］，其中bit［j］是三进制第j位的权值。
下面给出代码。comp_dp()函数中有3个for循环，第1个for循环3n次，后两个分别循环n次，总复杂度为O(3nn2)，当n=10时，正好通过OJ测试。
1#include<bits/stdc++.h>
2const int INF = 0x3f3f3f3f;
3using namespace std;
4int n,m;
5int bit［12］={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
6//三进制每位的权值。与二进制的0, 1, 2, 4, 8…对照理解
7int tri［60000］［11］;
8int dp［11］［60000］;
9int graph［11］［11］; //存图
10void make_trb(){ //初始化，求所有可能的路径
11 for(int i=0;i<59050;++i){ //共3^10 = 59050种路径状态
12 int t=i;
13 for(int j=1; j<=10; ++j){ tri［i］［j］=t%3;t/=3; }
14 }
15}
16int comp_dp(){
17int ans = INF;
18memset(dp, INF, sizeof(dp));
19for(int j=0;j<=n;j++)
20dp［j］［bit［j］］=0;//初始化： 从第j座城市出发，只访问j，费用为0
21for(int i=0;i<bit［n+1］;i++){//遍历所有路径，每个i是一条路径
22int flag=1; //所有城市都遍历过一次以上
23for(int j=1;j<=n;j++){//遍历城市，以j为起点
24if(tri［i］［j］ == 0){ //是否有一座城市访问次数为0
25flag=0; //还没有经过所有点
26continue;
27}
28for(int k=1; k<=n; k++){//遍历路径i-j的所有城市
29int l=i-bit［j］; //从路径i中去掉第j座城市
30dp［j］［i］=min(dp［j］［i］,dp［k］［l］+graph［k］［j］);
31}
32}
33if(flag)//找最小费用
34 for(int j=1; j<=n; j++)
35 ans = min(ans,dp［j］［i］); //路径i上最小的总费用
36}
37return ans;
38}
39int main(){
40make_trb();
41while(cin>>n>>m){
42memset(graph,INF,sizeof(graph));
43while(m--){
44int a,b,c; cin>>a>>b>>c;
45if(c<graph［a］［b］)graph［a］［b］=graph［b］［a］=c;
46}
47int ans = comp_dp();
48if(ans==INF) cout<<"-1"<<endl;
49else cout<<ans<<endl;
50}
51return 0;
52}
【习题】
洛谷P1433/P2831/P2704/P1879/P1896/P3092/P3694/P4925/P2157/P2167/P2396/P4363/P5005/P2150。
扫一扫
视频讲解
5.5区间DP
区间DP是常见的DP应用场景。区间DP也是线性DP，它把区间当成DP的阶段，用区间的两个端点描述状态和处理状态的转移。区间DP的主要思想是先在小区间进行DP得到最优解，然后再合并小区间的最优解求得大区间的最优解。解题时，先解决小区间问题，然后合并小区间，得到更大的区间，直到解决最后的大区间问题。合并的操作一般是把左右两个相邻的子区间合并。
区间DP的计算量比较大。一个长度为n的区间，编程时，区间DP至少需要两层for循环，第1层的i从区间的首部或尾部开始； 第2层的j从i开始到结束，i和j一起枚举出所有的子区间。所以，区间DP的复杂度大于O(n2)，一般为O(n3)。
很多区间DP问题可以用四边形不等式优化，把复杂度降为O(n2)。
5.5.1石子合并问题和两种模板代码
区间DP的经典例子是石子合并问题，下面用这个例子解释区间DP的概念，并给出模板代码。
例5.11石子合并
问题描述： 有n堆石子排成一排，每堆石子有一定的数量。将n堆石子合并成一堆，每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求最小总花费。
输入： 第1行输入整数n，表示有n堆石子。第2行输入n个数，分别表示这n堆石子的数目。
输出： 最小总花费。
输入样例：
3
2 4 5输出样例：
17
样例的计算过程是第1次合并2+4=6； 第2次合并6+5=11； 总花费为6+11=17。
本题不能用贪心法求解，下面指出原因。先回顾贪心法，它的应用场景是能从局部最优扩展到全局最优。
(1) 如果石子堆没有顺序，可以任意合并，用贪心法每次选择最小的两堆合并。
(2) 本题要求只能合并相邻的两堆，不能用贪心法。贪心操作是每次合并时找石子数相加最少的两堆相邻石子。例如，环形石子堆，初始是{2，4，7，5，4，3}，用贪心法得到最小花费64，但是另一种方法的结果为63，如表5.2所示。
表5.2贪心法对比
步骤
贪心法（方法1）方法2
花费剩余石子堆花费剩余石子堆
初始—2，4，7，5，4，3—2，4，7，5，4，3
155，4，7，5，466，7，5，4，3
299，7，5，41313，5，4，3
399，7，9713，5，7
41616，91213，12
525252525
总花费6463
下面用DP求解。
定义dp［i］［j］为合并第i堆到第j堆的最小花费。
状态转移方程为
dp［i］［j］=min{dp［i］［k］+dp［k+1］［j］+w［i］［j］}，i≤k <j
dp［1］［n］就是答案。方程中的w［i］［j］表示从第i堆到第j堆的石子总数。
按自顶向下的思路分析状态转移方程，很容易理解。计算大区间［i，j］的最优值时，合并它的两个子区间［i，k］和［k+1，j］，对所有可能的合并(i≤k<j，即k在i和j之间滑动)，采用最优的合并。子区间再分解为更小的区间，最小的区间［i，i+1］只包含两堆石子。
编程用自底向上递推的方法，先在小区间进行DP得到最优解，然后再逐步合并小区间为大区间。下面给出求dp［i］［j］的代码，其中包含i、j、k的3层循环，时间复杂度为O(n3)。第1个循环j是区间终点，第2个循环i是区间起点，第3个循环k在区间内滑动。注意，起点i应该从j-1开始递减，也就是从最小的区间［j-1，j］开始，逐步扩大区间。i不能从1开始递增，那样就是从大区间到小区间了。
1for(int i=1; i<=n; i++) dp［i］［i］ = 0;//n为石子堆数。初始化
2for(int j=2; j<=n; j++)// 区间［i,j］的终点j，i<j<=n
3for(int i=j-1;i>=1;i--) {// 区间［i,j］的起点i
4dp［i］［j］=INF;//初始化为极大值
5for(int k=i;k<j;k++) //大区间［i,j］从小区间［i,k］和［k+1,j］转移而来
6dp［i］［j］ = min(dp［i］［j］, dp［i］［k］ + dp［k+1］［j］ + w［i］［j］);
7}
下面给出另一种写法，它的i、j、k都是递增的，更容易理解，推荐使用这种写法。代码中用了一个辅助变量len，它等于当前处理的区间［i，j］的长度。dp［i］［j］是大区间，它需要从小区间dp［i］［k］和dp［k+1］［j］转移而来，所以应该先计算出小区间，才能根据小区间计算出大区间。len就起到了这个作用，从最小的区间len=2开始，此时区间［i，j］为［i，i+1］； 最后是最大区间len=n，此时区间［i，j］为［1，n］。
1for(int i=1; i<=n; i++)dp［i］［i］ = 0;
2for(int len=2; len<=n; len++) //len为区间［i,j］的长度，从小区间扩展到大区间
3for(int i=1; i<=n-len+1; i++){// 区间起点i
4int j = i + len - 1;// 区间终点j，i<j<=n
5dp［i］［j］ = INF;
6for(int k=i; k<j; k++)
7dp［i］［j］ = min(dp［i］［j］, dp［i］［k］ + dp［k + 1］［j］ + w［i］［j］);
8}
上述代码的复杂度为O(n3)，不太好。区间DP常常可以用四边形不等式进行优化，把复杂度性能提升到O(n2)，详见5.10节。经典例题“石子合并”也在5.10节进行了更多讲解。当然，不是所有的区间DP都能做四边形不等式优化。
5.5.2区间DP例题
下面给出几道经典区间DP例题。请读者在看题解之前，自己思考并写出代码，一定会大有收获。
1. hdu 2476
例5.12String painter(hdu 2476)
问题描述： 给定两个长度相等的字符串A、B，由小写字母组成。一次操作，允许把A中的一个连续子串(区间)都转换为某个字符(就像用刷子刷成一样的字符)。要把A转换为B，问最少操作数是多少?
输入： 第1行输入字符串A，第2行输入字符串B。两个字符串的长度不大于100。
输出： 一个表示答案的整数。
输入样例：
zzzzzfzzzzz
abcdefedcba输出样例：
6
第1次把zzzzzfzzzzz转换为aaaaaaaaaaa，第2次转换为abbbbbbbbba，第3次转换为abccccccccba…
这道经典例题能帮助读者深入理解区间DP是如何构造和编码的。
1) 从空白串转换到B
先考虑一个简单的问题： 从空白串转换到B。为方便阅读代码，把字符串存储为B［1］~B［n］，不用B［0］~B［n-1］，编码时这样输入： scanf("%s%s"，A+1，B+1)。
如何定义DP状态？可以定义dp［i］表示在区间［1，i］内转换为B的最少操作次数。或者更进一步，定义dp［i］［j］表示在区间［i，j］内从空白串转换到B时的最少操作次数。重点是区间［i，j］两端的字符B［i］ 和B［j］，分析以下两种情况。
(1) B［i］=B［j］。第1次用B［i］把区间［i，j］刷一遍，这个刷法肯定是最优的。如果分别去掉两个端点，得到两个区间［i+1，j］和［i，j-1］，这两个区间的最少操作次数相等，也等于原区间［i，j］的最少操作次数。例如，B="abbba"，先用"a"全部刷一遍，再刷一次"bbb"，共刷两次。如果去掉第1个"a"，剩下的"bbba"也是刷两次。
(2) B［i］≠B［j］。因为两个端点不同，至少要各刷一次。用标准的区间操作，把区间分成［i，k］和［k+1，j］两部分，枚举最少操作次数。
2) 从A转换到B
如何求dp［1］［j］？观察A和B相同位置的字符，分析以下两种情况。
(1) A［j］=B［j］。这个字符不用转换，有dp［1］［j］=dp［1］［j-1］。
(2) A［j］≠B［j］。仍然用标准的区间DP，把区间分成［1，k］和［k+1，j］两部分，枚举最少操作次数。这里利用了从空白串转换到B的结果，当区间［k+1，j］内A和B的字符不同时，从A转换到B与从空白串转换到B是等价的。
下面给出hdu 2476的代码，其中，从空白串转换到B的代码完全套用了石子合并问题的编码。
1#include <bits/stdc++.h>
2using namespace std;
3char A［105］,B［105］;
4int dp［105］［105］;
5const int INF = 0x3f3f3f3f;
6int main() {
7while(~scanf("%s%s", A+1, B+1)){
8int n = strlen(A+1); //输入A, B
9for(int i=1;i<=n;i++) dp［i］［i］=1;//初始化
10//先从空白串转换到B
11for(int len=2; len<=n; len++)
12for(int i=1; i<=n-len+1; i++){
13int j = i + len-1;
14dp［i］［j］ = INF;
15if(B［i］ == B［j］)//区间［i, j］两端的字符相同,B［i］ = B［j］
16dp［i］［j］ = dp［i+1］［j］;//或者dp［i］［j］ = dp［i］［j-1］)
17 else//区间［i, j］两端的字符不同B［i］ ≠ B［j］
18 for(int k=i; k<j; k++)
19 dp［i］［j］ = min(dp［i］［j］, dp［i］［k］ + dp［k+1］［j］);
20}
21//下面从A转换到B
22for(int j=1; j<=n; ++j){
23if(A［j］ == B［j］)dp［1］［j］ = dp［1］［j-1］;//字符相同，不用转换
24else
25 for(int k=1; k<j; ++k)
26 dp［1］［j］ = min(dp［1］［j］, dp［1］［k］ + dp［k+1］［j］);
27}
28printf("%d＼n",dp［1］［n］);
29}
30return 0;
31}
2. hdu 4283
例5.13You are the one(hdu 4283)
问题描述： n个男孩去相亲，排成一队上场。大家都不想等，排队越靠后越愤怒。每人的耐心不同，用D表示火气，设男孩i的火气为Di，他排在第k个时，愤怒值为(k-1)Di。
主持人不想看到会场气氛紧张。他安排了一间黑屋，可以调整这排男孩上场的顺序，屋子很狭长，先进去的男孩最后出来(相当于一个堆栈)。例如，当男孩A排到时，如果他后面的男孩B火气更大，就把A送进黑屋，让B先上场。一般情况下，那些火气小的男孩要多等等，让火气大的占便宜。不过，零脾气的你也不一定吃亏，如果你原本排在倒数第2个，而最后一个男孩脾气最坏，主持人为了让这个坏家伙第1个上场，把其他人全赶进了黑屋，结果你就排在了黑屋的第1名，将第2个上场。
注意，每个男孩都要进出黑屋。
对所有男孩的愤怒值求和，求所有可能情况的最小总愤怒值。
输入： 第1行输入一个整数T，即测试用例的数量。对于每种情况，第1行输入n(0<n≤100)，后面n行中，输入整数D1~Dn表示男孩的火气(0≤Di≤100)。
输出： 对每个用例，输出最小总愤怒值之和。
读者可以试试用栈来模拟，这几乎是不可能的。这是一道区间DP例题，巧妙地利用了栈的特性。
定义dp［i］［j］表示从第i个人到第j个人，即区间［i，j］的最小总愤怒值。
由于栈的存在，本题的区间［i，j］的分割点k比较特殊。分割时，总是用区间［i，j］的第1个元素i把区间分成两部分，让i第k个从黑屋出来上场，即第k个出栈。根据栈的特性，若第1个元素i第k个出栈，则第2~k-1个元素肯定在第1个元素之前出栈，第k+1~j个元素肯定在第k个之后出栈https://blog.csdn.net/weixin_41707869/article/details/99686868。
例如，5个人的排队序号是1，2，3，4，5。如果第1(i=1)个人要第3(k=3)个出场，那么栈的操作是这样： 1号进栈→2号进栈→3号进栈→3号出栈→2号出栈→1号出栈。2号和3号在1号之前出栈，1号第3个出栈，4号和5号在1号后面出栈。
分割点k(1≤k≤j-i+1)把区间划分成两段，即dp［i+1］［i+k-1］和dp［i+k］［j］。dp［i］［j］的计算分为以下3部分。
(1) dp［i+1］［i+k-1］。原来i后面的k-1个人现在排到i前面了。
(2) D［i］(k-1)。第i个人往后挪了k-1个位置，愤怒值增加D［i］(k-1)。
(3) dp［i+k］［j］+k(sum［j］-sum［i+k-1］)。第k个位置后面的人，即区间［i+k，j］的人，由于都在前k个人之后，相当于从区间的第1个位置往后挪了k个位置，所以整体愤怒值要加上k(sum［j］-sum［i+k-1］)。其中，sum［j］=∑ji=1Di为1~j所有人火气值的和，sum［j］-sum［i+k-1］是区间［i+k，j］内人的火气值的和。
代码完全套用石子合并的模板。其中，DP方程给出了两种写法，对照看更清晰。
1for(int len=2; len<=n; len++)
2for(i=1;i<=n-len+1;i++) {
3j = len + i - 1;
4dp［i］［j］ = INF;
5for(int k=1;k<=j-i+1;k++)//k： i往后挪了k位，这样写容易理解
6dp［i］［j］ = min(dp［i］［j］, dp［i+1］［i+k-1］ + D［i］*(k-1)
7+ dp［i+k］［j］ + k*(sum［j］-sum［i+k-1］)); //DP方程
8//for(int k=i;k<=j;k++)//或者这样写，k为整个队伍的绝对位置
9//dp［i］［j］ = min(dp［i］［j］, dp［i+1］［k］ + D［i］*(k-i)
10// + dp［k+1］［j］ + (k-i+1)*(sum［j］-sum［k］));
11}
5.5.3二维区间DP
前面例子中的区间［i，j］可以看作在一条直线上移动，即一维DP。下面给出一道二维区间DP的例题，它的区间同时在两个方向移动。
例5.14Rectangle painting 1(CF1199F)https://codeforces.com/contest/1199/problem/F，如果CodeForces很慢，用代理提交
(https://vjudge.net/problem/CodeForces1199F)。
问题描述： 有一个n×n大小的方格图，某些方格初始为黑色，其余为白色。一次操作，可以选定一个h×w的矩形，把其中所有方格涂成白色，代价是max(h，w)。要求用最小的代价把所有方格涂成白色。
输入： 第1行输入整数n，表示方格的大小。后面有n行，每行输入长度为n的串，包含符号'.'和'#'，'.'表示白色，'#'表示黑色。第x行第y列的坐标是(x，y)。n≤50。
输出： 打印一个整数，表示把所有方格涂成白色的最小代价。
输入样例：
5
#...#
#.#.
......
.#...
#....输出样例：
5
设矩形区域从左下角坐标(x1，y1)到右上角坐标(x2，y2)。定义状态dp［x1］［y1］［x2］［y2］表示把这个区域涂成白色的最小代价。
这个区域可以分别按x轴或按y轴分割成两个矩形，遍历所有可能的分割，求最小代价。从x方向看，是一个区间DP； 从y方向看，也是一个区间DP。
代码可以完全套用一维DP的模板，分别在两个方向上操作。
(1) x方向，把区间分为［x1，k］和［k+1，x2］。状态转移方程为
dp［x1］［］［x2］［］=min(dp［x1］［］［x2］［］，dp［x1］［］［k］［］+dp［k+1］［］［x2］［］)
(2) y方向，把区间分为［y1，k］和［k+1，y2］。状态转移方程为
dp［］［y1］［］［y2］=min(dp［］［y1］［］［y2］，dp［］［y1］［］［k］+dp［］［k+1］［］［y2］)
下面给出代码，有5层循环，时间复杂度为O(n5)。对比一维区间DP，有3层循环，复杂度为O(n3)。
1//代码改写自https://www.cnblogs.com/zsben991126/p/11643832.html
2#include<bits/stdc++.h>
3using namespace std;
4#define N 55
5int dp［N］［N］［N］［N］;
6char mp［N］［N］; //方格图
7int main(){
8int n;cin>>n;
9for(int i=1;i<=n;i++)
10for(int j=1;j<=n;j++) cin>>mp［i］［j］;
11for(int i=1;i<=n;i++)
12for(int j=1;j<=n;j++)
13if(mp［i］［j］=='.')dp［i］［j］［i］［j］=0; //白格不用涂
14else dp［i］［j］［i］［j］=1; //黑格(i,j)涂成白色，需一次
15for(int lenx=1;lenx<=n;lenx++) //len从1开始，不是2，因为有x和y两个方向
16for(int leny=1;leny<=n;leny++)
17for(int x1=1;x1<=n-lenx+1;x1++)
18for(int y1=1;y1<=n-leny+1;y1++){
19int x2 = x1+lenx-1;//x1为x轴起点，x2为x轴终点
20int y2 = y1+leny-1;//y1为y轴起点，y2为y轴终点
21if(x1==x2 && y1==y2) continue; //lenx=1且leny=1的情况
22dp［x1］［y1］［x2］［y2］ = max(abs(x1-x2),abs(y1-y2)) + 1; //初始值
23for(int k=x1;k<x2;k++) //枚举x方向，y不变，区间［x1,k］+［k+1,x2］
24dp［x1］［y1］［x2］［y2］ = min(dp［x1］［y1］［x2］［y2］,
25dp［x1］［y1］［k］［y2］+dp［k+1］［y1］［x2］［y2］);
26for(int k=y1;k<y2;k++) //枚举y方向，x不变，区间［y1,k］+［k+1,y2］
27dp［x1］［y1］［x2］［y2］ = min(dp［x1］［y1］［x2］［y2］,
28dp［x1］［y1］［x2］［k］+dp［x1］［k+1］［x2］［y2］);
29}
30cout << dp［1］［1］［n］［n］;
31}
【习题】
(1) 力扣： https://leetcodecn.com/circle/article/NfHhXD/。
(2) 区间DP(kuangbin带你飞)： https://vjudge.net/contest/77874。
(3) 洛谷 P1880/P3146/P1063/P1005/P4170/P4302/P2466。
扫一扫
视频讲解
5.6树形DP
在树这种数据结构上做DP很常见： 给出一棵树，要求以最少代价(或最大收益)完成给定的操作。在树上做DP显得非常自然，因为树本身有“子结构”性质(树和子树)，具有递归性，符合5.1.2节提到的“记忆化递归”的思路，所以树形DP一般就这样编程。
基于树的解题步骤一般是先把树转换为有根树(如果是几棵互不连通的树，就加一个虚拟根，它连接所有孤立的树)，然后在树上做DFS，递归到最底层的叶子节点，再一层层返回信息更新至根节点。显然，树上DP所操作的就是这一层层返回的信息。不同的题目需要灵活设计不同的DP状态和转移方程。
树需要用数据结构来存储。关于树的存储方式，请提前阅读本书10.1节“图的存储”。
5.6.1树形DP的基本操作
先看一道简单的入门题，了解树的存储以及如何在树上设计DP和进行状态转移。请读者特别注意DP设计时的两种处理方法： 二叉树、多叉树。
例5.15二叉苹果树(洛谷P2015)
问题描述： 有一棵苹果树，如果树枝有分叉，一定是分两叉。这棵树共有n个节点，编号为1~n，树根编号为1。用一根树枝两端连接的节点的编号描述一根树枝的位置，下面是一棵有4根树枝的树：
2 5
\\ /
3 4
\\ /
1
这棵树的枝条太多了，需要剪枝。但是一些树枝上长有苹果，最好别剪。给定需要保留的树枝数量，求出最多能留住多少个苹果。
输入： 第1行输入两个数n和q(1≤q≤n，1<n≤100)，n表示树的节点数，q表示要保留的树枝数量。接下来n-1行描述树枝的信息。每行输入3个整数，前两个数是它连接的节点的编号，第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。
输出： 最多能留住的苹果的数量。
首先是树的存储，在计算之前需要先存储这棵树。树是图的一种特殊情况，树的存储和图的存储相似： 一种方法是邻接表，用vector实现又简单又快； 另一种方法是链式前向星，对空间要求很高时可以使用，编码也不算复杂。本题给出的代码用vector存储树。
本题的求解从根开始自顶向下，是典型的DP思路。
1. DP状态和DP状态转移方程
定义状态dp［u］［j］表示以节点u为根的子树上留j条边时的最多苹果数量。dp［1］［q］就是答案。
状态转移方程如何设计？下面给出两种思路： 二叉树方法、多叉树(一般性)方法。
1) 二叉树
根据二叉树的特征，考虑u的左右子树，如果左儿子lson留k条边，右儿子rson就留j-k条边，用k在［0，j］内遍历不同的分割。读者可以尝试用这种思路写出记忆化搜索的代码，主要步骤参考下面的代码。
int dfs(int u, int j){ //以u为根的子树，保留j个树枝时的最多苹果
if(dp［u］］［j］ >=0)return dp［u］［j］;//记忆化，如果已计算过，就返回
for(int k=0; k<j; k++) //用k遍历
dp［u］［j］ = max(dp［u］［j］, dfs(u.lson,k) + dfs(u.rson, j-k)); //左右儿子合起来
return dp［u］［j］;
}
2) 多叉树
由于局限于二叉树这种结构，下面用多叉树实现，这是一般性的方法。把状态转移方程写成如下形式。
for(int j = sum［u］; j >= 0; j--) //sum［u］为以u为根的子树上的总边数
for(int k = 0; k <= j - 1; k++)//用k遍历不同的分割
dp［u］［j］ = max(dp［u］［j］, dp［u］［j-k-1］ + dp［v］［k］ + w); //状态转移方程
其中，v是u的一个子节点。dp［u］［j］的计算分为以下两部分。
(1) dp［v］［k］： 在v上留k条边。
(2) dp［u］［j-k-1］： 除了v上的k条边，以及［u,v］边，那么以u为根的这棵树上还有j-k-1条边，它们在u的其他子节点上。
下面给出代码。
1//洛谷P2015的代码(邻接表存树)
2#include<bits/stdc++.h>
3using namespace std;
4const int N = 200;
5struct node{
6int v, w; //v是子节点，w是边［u,v］的值
7node(int v = 0, int w = 0) : v(v), w(w) {}
8};
9vector<node> edge［N］;
10int dp［N］［N］, sum［N］; //sum［i］记录以i为根的子树的总边数
11int n, q;
12void dfs(int u, int father){
13for(int i = 0; i < edge［u］.size(); i++) {//用i遍历u的所有子节点
14int v = edge［u］［i］.v, w =edge［u］［i］.w;
15if(v == father) continue;//不回头搜索父亲，避免循环
16dfs(v, u); //递归到最深的叶子节点，然后返回
17sum［u］ += sum［v］ + 1;//子树上的总边数
18//for(int j=sum［u］;j>=0;j--)
19//for(int k=0;k<=j-1;k++)//两个for优化为以下代码，不优化也可以
20for(int j = min(q, sum［u］); j >= 0; j--)
21for(int k = 0; k <= min(sum［v］, j - 1); k++)
22dp［u］［j］ = max(dp［u］［j］, dp［u］［j-k-1］ + dp［v］［k］ + w);
23}
24}
25int main(){
26scanf("%d%d", &n, &q);//n个点，留q根树枝
27for(int i = 1; i < n; i++){
28int u, v, w;scanf("%d%d%d", &u, &v, &w);
29edge［u］.push_back(node(v,w)); //把边［u,v］存到u的邻接表中
30edge［v］.push_back(node(u,w)); //无向边
31}
32dfs(1, 0);//从根节点开始做记忆化搜索
33printf("%d＼n", dp［1］［q］);
34return 0;
35}
2. 二叉树和多叉树的讨论
本题是二叉树应用，但是上面的代码是按多叉树处理的。代码中用v遍历了u的所有子树，并未限定是二叉树。状态方程计算dp［u］［j］时包含两部分： dp［u］［j-k-1］和dp［v］［k］，其中dp［v］［k］是u的一棵子树v，dp［u］［j-k-1］是u的其他所有子树。
上面代码中最关键的是dfs()函数中j的循环方向，它应该从sum［u］开始递减，而不是从0开始递增。例如，计算dp［u］［5］，它用到了dp［u］［4］、dp［u］［3］等，它们可能是有值的，原值等于以前用u的另一棵子树计算得到的结果，也就是排除当前的v这个子树时计算的结果。
(1) 让j递减循环是正确的。例如，先计算j=5，dp［u］［5］用到了dp［u］［4］、dp［u］［3］等，它们都是正确的原值； 下一步计算j=4时，新的dp［u］［4］会覆盖原值，但是不会影响到对dp［u］［5］的计算。
(2) 让j递增循环是错误的。例如，先计算j=4，得到新的dp［u］［4］； 再计算dp［u］［5］，这时需要用到dp［u］［4］，而此时的dp［u］［4］已经不再是正确的原值了。
读者可以联想5.1.4节的“自我滚动”编程，它的循环也是从大到小递减的。两者的原理一样，即新值覆盖原值的问题。
k的循环顺序则无所谓，它是［0，j-1］区间的分割，从0开始递增或从j-1开始递减都可以。
两个for循环还可以做一些小优化，详情见代码。
复杂度分析： dfs()函数递归到每个节点，每个节点有两个for循环，总复杂度小于O(n3)。
3. 树形DP例题
例5.16没有上司的舞会(洛谷P1352)
问题描述： 某单位有n个职员，编号为1~n。他们之间有从属关系，也就是说他们的关系就像一棵以老板为根的树，父节点就是子节点的直接上司。现在有一个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数ri，但是如果某个职员的直接上司来参加舞会，那么这个职员就无论如何也不肯来参加舞会了。编程计算邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入： 第1行输入一个整数n。第2~n+1行中，每行输入一个整数，第i+1行的整数表示职员i的快乐指数ri。第n+2~2n行中，每行输入两个整数l和k，代表k是l的直接上司。
输出： 输出一行一个整数代表最大的快乐指数。
这也是一道经典题。一个节点表示一个职员，如果一个节点代表的职员参加宴会，那么他的子节点就不能参加宴会； 如果不参加宴会，他的子节点参不参加都行。根据DP的解题思路，定义状态：
dp［i］［0］表示不选择当前节点(不参加宴会)的最优解；
dp［i］［1］表示选择当前节点(参加宴会)的最优解。
状态转移方程有两种情况。
(1) 不选择当前节点，那么它的子节点可选可不选，取其中的最大值，即
dp［u］［0］+=max(dp［v］［0］，dp［v］［1］)
(2) 选择当前节点，那么它的子节点不能选，即
dp［u］［1］+=dp［v］［0］
代码包含3部分： ①建树，用STL vector 生成链表，建立关系树； ②树的遍历，用DFS从根节点开始进行记忆化搜索； ③DP。
复杂度分析： 遍历每个节点，总复杂度为O(n)。
1#include<bits/stdc++.h>
2using namespace std;
3const int N = 6005;
4int val［N］, dp［N］［2］, father［N］;
5vector <int> G［N］;
6void addedge(int from,int to){
7G［from］.push_back(to);//用邻接表建树
8father［to］ = from; //父子关系
9}
10void dfs(int u){
11dp［u］［0］ = 0;//赋初值： 不参加宴会
12dp［u］［1］ = val［u］; //赋初值： 参加宴会
13//for(int i=0;i<G［u］.size();i++){//遍历u的邻居v，逐一处理这个父节点的每个子节点
14//int v = G［u］［i］;
15for(int v : G［u］){ //这一行和上面两行的作用一样
16dfs(v);//DFS子节点
17dp［u］［1］ += dp［v］［0］;//父节点选择，子节点不选
18dp［u］［0］ += max(dp［v］［0］, dp［v］［1］); //父节点不选，子节点可选可不选
19 }
20}
21int main(){
22int n; scanf("%d",&n);
23for(int i=1;i<=n;i++) scanf("%d",&val［i］); //输入快乐指数
24for(int i=1;i<n;i++){
25int u,v;scanf("%d%d",&u,&v);
26addedge(v,u);
27}
28int t = 1;
29while(father［t］) t = father［t］; //查找树的根节点
30dfs(t); //从根节点开始，用DFS遍历整棵树
31printf("%d＼n", max(dp［t］［0］, dp［t］［1］));
32return 0;
33}
5.6.2背包与树形DP
有一些树形DP问题可以抽象为背包问题，称为“树形依赖的背包问题”。例如,5.6.1节的“二叉苹果树”问题，可以建模为“分组背包”(注意与普通分组背包的区别，这里的每个组可以选多个物品，而不是一个)，具体如下。
(1) 分组。根节点u的每个子树是一个分组。
(2) 背包的容量。把以u为根的整棵树上的树枝数看作背包容量。
(3) 物品。把每个树枝看作一个物品，体积为1，树枝上的苹果数量看作物品的价值。
(4) 背包目标。能放入背包的物品的总价值最大，就是留在树枝上的苹果数最多。
如果做个对比，会发现分组背包的代码和“二叉苹果树”的代码很像，下面给出两段代码作为对比。
(1) 分组背包的代码。参考5.2节分组背包例题hdu 1712。
1for(int i = 1; i <= n; i++) //遍历每个组
2for(int j = C; j>=0; j--) //背包总容量C
3for(int k = 1; k <= m; k++) //用k遍历第i组的所有物品
4if(j >= c［i］［k］)//第k个物品能装进容量j的背包
5 dp［j］ = max(dp［j］, dp［j-c［i］［k］］ + w［i］［k］);//第i组第k个
(2) 树形DP代码。下面是洛谷P2015部分代码。
1for(int i = 0; i < edge［u］.size(); i++) {//把u的每个子树看作一个组
2...
3for(int j = sum［u］; j >= 0; j--) //把u的树枝总数看成背包容量
4for(int k = 0; k <= j - 1; k++)//用k遍历每个子树的每个树枝
5dp［u］［j］ = max(dp［u］［j］, dp［u］［j-k-1］ + dp［v］［k］ + w);
注意代码(1)和代码(2)的j循环都是从大到小，因为用到了“自我滚动”数组，在对应的章节中有详细解释。
树形背包问题的状态定义，一般用dp［u］［j］表示以点u为根的子树中选择j个点(或j条边)的最优情况。
下面给出一道经典题，请读者自己分析和编码。
例5.17有线电视网(洛谷P1273，poj 1155)
问题描述： 某收费有线电视网计划转播一场足球比赛。他们的转播网和用户终端构成一个树状结构，这棵树的根节点位于足球比赛的现场，叶子节点为各个用户终端，其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用用于观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号，不给哪些用户提供信号。写一个程序，找出一个方案，使有线电视网在不亏本的情况下使观看转播的用户尽可能多。
输入： 第1行输入两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的节点总数，M为用户终端的数量。第1个转播站即树的根节点，编号为1，其他转播站编号为2~N-M，用户终端编号为N-M+1~N。接下来的N-M行中，每行的输入表示一个转播站的数据，第i+1行表示第i个转播站的数据，其格式为
k A1 C1 A2 C2 … Ak Ck
其中，k表示该转播站下接k个节点(转播站或用户)，每个节点对应一对整数A与C，A表示节点编号，C表示从当前转播站传输信号到节点A的费用。最后一行输入所有用户为观看比赛而准备支付的钱数。
输出： 输出一个整数，表示符合条件的最大用户数。
本题与洛谷P2015类似。
定义dp［u］［j］表示以u为根的子树上有j个用户时的最小费用。计算结束后，使dp［1］［j］≤0的最大j就是答案。
状态转移方程为dp［u］［j］=max(dp［u］［j］，dp［u］［j-k］+dp［v］［k］+w)，与洛谷P2015的状态转移方程几乎一样。
【习题】
本节用几道简单例题介绍了树形DP的基本操作。树形DP的题目往往较难，请读者多练习。
(1) 经典题： hdu 1520、hdu 2196(在《算法竞赛入门到进阶》中有详细讲解)。
(2) 树形背包： poj 1947/2486，hdu 1011/1561/4003。
(3) 洛谷P4322/P1352/P1040/P1122/P1273/P2014/P2585/P3047/P3698/P5658/P2607/P3177/P4395/P4516。
扫一扫
视频讲解
5.7一 般 优 化
DP是一种非常优秀的算法思想，它通过“重叠子问题、最优子结构、无后效性”实现了高效的算法。DP的效率取决于3方面： ①状态总数； ②每个状态的决策数； ③状态转移计算量。这3方面都可以进行优化。
(1) 状态总数的优化。相当于搜索的各种剪枝，去除无效状态;使用降维，设计DP状态时尽量用低维的DP。
(2) 减少决策数量，即状态转移方程的优化，如四边形不等式优化、斜率优化。
(3) 状态转移计算量的优化，如用预处理减少递推时间； 用Hash表、单调队列、线段树减少枚举时间等。
本节先介绍几种简单优化方法，后面几节再介绍几种高级优化方法。
1. 倍增优化
动态规划是多阶段递推，可以用倍增法将阶段性的线性增长加快为成倍增长。2.5节的ST算法就是倍增优化的DP。5.2节中多重背包的二进制拆分优化也是典型的倍增优化。
2. 树状数组优化
如果题目与简单的区间操作有关，如区间查询、区间修改等，区间操作可以用树状数组或线段树来处理，把区间操作复杂度优化到O(log2n)，从而降低总复杂度。这种题目的基本思路是先定义DP状态和状态转移方程，然后思考如何对方程进行优化。
下面给出一道树状数组优化的例题。
例5.18方伯伯的玉米田(洛谷P3287)
问题描述： 有一个包含n个正整数的序列，做0~k次操作，每次任选一个区间，把区
间内的所有数加1。最后任意去掉一些数字。问最多能剩下多少数字，构成一个单调不下降序列？
输入： 第一行输入两个整数n和k，分别表示数字的数目和最多操作次数。第2行输入n个整数ai(i=1,2,…,n)，表示序列中的n个数字。
输出： 一个整数，表示最多剩下多少数字。
数据范围： 1<n<10000，1<k≤500，1≤ai≤5000。
最长单调不下降序列是一个典型的DP问题，和5.2节中的最长递增子序列(LIS)相似。本题加上了区间操作，可以用高级数据结构提高区间操作的效率。
设序列存储于a［1］~a［n］。区间操作可以进行简化： 在区间［L，R］内加1的操作，应该把右端点R设置成最后一个位置n，也就是说，每次操作的区间是［L，n］。因为： ①如果R不是最后位置，对区间［L，R］加1，会导致R后面的数相对变小，不利于形成更长的单调不下降序列； ②如果R是最后位置，至少不会影响整个序列的单调不下降状态。
先回顾最长递增子序列(LIS)问题，定义状态dp［i］表示以第i个数为结尾的最长递增子序列的长度，状态转移方程为dp［i］=max{dp［j］}+1,0<j<i,a［j］<a［i］，答案是max{dp［i］}。
本题结合了区间操作，定义dp［i］［j］表示做过j次区间操作，每次操作的起点都不超过i，且以i为结尾的LIS的长度。状态转移方程为
dp［i］［j］=max{dp［x］［y］+1}x<i，y≤j，a［x］+y≤a［i］+j
这是一个二维区间问题，直接计算需要i、j二重循环。回顾4.2.3节二维树状数组例题对二维区间的处理，发现本题类似。树状数组可以把区间查询和更新复杂度优化到O(log2n)。
下面给出代码，是二维树状数组和LIS的结合。分析时间复杂度，在main()函数中有n、k两个循环，循环内用树状数组执行query()和update()，总复杂度约为O(nklog2klog2n)。
1//代码改写自www.luogu.com.cn/blog/361308/solution-p3287
2#include<bits/stdc++.h>
3using namespace std;
4#define lowbit(x)((x) & - (x))
5int a［10005］, dp［10005］［505］, t［505］［5505］, n, k;
6void update(int x, int y, int d) { //更新区间
7for (int i=x; i <= k + 1; i += lowbit(i))
8for (int j=y; j <= 5500; j += lowbit(j))
9t［i］［j］ = max(t［i］［j］, d);
10}
11int query(int x, int y) { //查区间最大值
12int ans=0;
13for (int i=x; i>0; i -= lowbit(i))
14for (int j=y; j>0; j -= lowbit(j))
15ans = max(ans, t［i］［j］);
16return ans;
17}
18int main() {
19scanf("%d%d", &n, &k);
20for (int i=1; i <= n; i++) scanf("%d", &a［i］);
21for (int i=1; i <= n; i++)
22for (int j=k; j>=0; j--){
23dp［i］［j］ = query(j+1, a［i］+j) + 1;
24update(j+1, a［i］+j, dp［i］［j］);
25}
26printf("%d", query(k+1, 5500));
27return 0;
28}
3. 线段树优化
用下面的例题说明线段树DP优化的做法。
例5.19基站选址(洛谷P2605)
问题描述： 有n个村庄位于一条直线上，第i个村庄距离第1个村庄的距离为Di。要在这n个村庄中建不超过k个基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个基站，那么村庄就被基站覆盖。如果第i个村庄没有被覆盖，需要补偿Wi。请选择基站位置，使总费用最少。
输入： 第1行输入两个整数n和k。第2行输入n-1个整数，分别表示D2，D3，…，Dn。第3行输入n个整数，分别表示C1，C2，…，Cn。第4行输入n个整数，分别表示S1，S2，…，Sn。第5行输入n个整数，分别表示W1，W2，…，Wn。
输出： 最少总费用。
数据范围： k≤n，k≤100，n≤20000，Di≤109，Ci≤10000，Si≤109，Wi≤10000。
定义状态dp［i］［j］表示前i个村庄内第j个基站建在i处的最小费用。
状态转移方程为
dp［i］［j］=min{dp［k］［j-1］+pay［k］［i］}，j-1≤k<i
其中，pay［k］［i］表示区间［k，i］内没有被基站i、k覆盖的村庄的赔偿费用。
如果直接计算这个状态转移方程，需要做i、j、k三重循环，复杂度为O(n3)。如何优化？
(1) 滚动数组。发现状态转移方程中的j只与j-1有关，那么可以用滚动数组优化j，把复杂度降低为O(n2)。优化后的状态转移方程为
dp［i］=min{dp［k］+pay［k］［i］}，1≤k<i
(2) 区间操作的优化。方程中的pay［］［］计算［k，i］区间内的赔偿费用，是一个区间求和问题，用线段树维护。
本题的线段树代码很长，请读者自己完成。
扫一扫
视频讲解
5.8单调队列优化
单调队列是常见的DP优化技术，本节讲解基本的思路和方法。在5.9节中，单调队列也有关键的应用。
5.8.1单调队列优化的原理
先回顾单调队列的概念，它具有以下特征。
(1) 单调队列的实现。用双端队列实现，队头和队尾都能插入和弹出。手写双端队列很简单。
(2) 单调队列的单调性。队列内的元素具有单调性，从小到大，或者从大到小。
(3) 单调队列的维护。每个新元素都能进入队列，它从队尾进入队列时，为维护队列的单调性，应该与队尾比较，把破坏单调性的队尾弹出。例如，一个从小到大的单调队列，如果要入队的新元素a比原队尾v小，那么把v弹走，然后a继续与新的队尾比较，直到a比队尾大为止，最后a进入队尾。
单调队列在DP优化中的基本应用，是对这样一类DP状态转移方程进行优化：
dp［i］=min{dp［j］+a［i］+b［j］}，L(i)≤j≤R(i)
方程中的min也可以是max。方程的特点是其中关于i的项a［i］和关于j的项b［j］是独立的。j被限制在窗口［L(i)，R(i)］内，常见的如给定一个窗口值k，i-k≤j≤i。这个DP状态转移方程的编程实现，如果简单地对i做外层循环，对j做内层循环，复杂度为O(n2)。如果用单调队列优化，复杂度可提高到O(n)。
为什么单调队列能优化这个DP状态转移方程？
图5.18外层i和内层
j的循环
概括地说，单调队列优化算法能把内、外两层循环精简到一层循环。其本质原因是外层i变化时，不同的i所对应的内层j的窗口有重叠。如图5.18所示，i=i1时，对应的j1的滑动窗口(窗口内处理DP决策)范围是上方的阴影部分； i=i2时，对应的j2处理的滑动窗口范围是下方的阴影部分； 两部分有重叠。当i从i1增加到i2时，这些重叠部分被重复计算，如果减少这些重复，就得到了优化。如果把所有重叠的部分都优化掉，那么所有j加起来只从头到尾遍历了一次，此时j的遍历实际上就是i的遍历了。
在窗口内处理的这些决策，有以下两种情况。
(1) 被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。
(2) 未被排除的决策。内层循环j未排除的决策，在外层循环i增大时，仍然能按原来的顺序被用到。
那么可以用单调队列统一处理这些决策，从而精简到只用一个循环，得到优化。下面详细介绍单调队列的操作。
(1) 求一个dp［i］。i是外层循环，j是内层循环，在做内层循环时，可以把外层的i看作一个定值。此时，a［i］可以看作常量，把j看作窗口［L(i)，R(i)］内的变量，DP状态转移方程等价于
dp［i］=min{dp［j］+b［j］}+a［i］
问题转化为求窗口［L(i)，R(i)］内的最优值min{dp［j］+b［j］}。记ds［j］=dp［j］+b［j］，在窗口内，用单调队列处理ds［j］，排除不合格的决策，最后求得区间内的最优值，最优值即队首。得到窗口内的最优值后，就可以求得dp［i］。另外，队列中留下的决策，在i变化后仍然有用。
请注意，队列处理的决策ds［j］只与j有关，与i无关，这是本优化方法的关键。如果既与i有关，又与j有关，它就不能在下一步求所有dp［i］时得到应用。具体来说： ①如果ds［j］只与j有关，那么一个较小的i1操作的某个策略ds［j］与一个较大的i2操作的某个策略ds［j］是相等的，从而产生了重复性，可以优化； ②如果ds［］与i、j都有关，那么就没有重复性，无法优化。请结合后面的例题深入理解。
(2) 求所有dp［i］。考虑外层循环i变化时的优化方法。一个较小的i1所排除的ds［j］，在处理一个较大的i2时，也会被排除，重复排除其实没有必要； 一个较小的i1所得到的决策，仍能用于一个较大的i2。统一用一个单调队列处理所有i，每个ds［j］(提示： 此时j不再局限于窗口［L(i)，R(i)］，而是整个区间1≤j≤n，那么ds［j］实际上就是ds［i］了)都进入队列一次，并且只进入队列一次，总复杂度为O(n)。此时，内外层循环i、j精简为一个循环i。
5.8.2单调队列优化例题
1. 洛谷P2627
例5.20Mowing the lawn(洛谷P2627)
问题描述： 有一个包括n个正整数的序列，第i个整数为Ei，给定一个整数k，找这样的子序列，子序列中的数在原序列连续不能超过k个。对子序列求和，问所有子序列中最大的和是多少？1≤n≤100000，0≤Ei≤1000000000，1≤k≤n。
例如，n=5，原序列为{7，2，3，4，5}，k=2，子序列{7，2，4，5}有最大和18，其中的连续部分为{7,2}、{4,5}，长度都不超过k=2。
由于n较大，算法的复杂度应该小于O(n2)，否则会超时。
用DP求解，定义dp［i］为前i个整数的最大子序列和，状态转移方程为
dp［i］=max{dp［j-1］+sum［i］-sum［j］}，i-k≤j≤i
其中，sum［i］为前缀和，即从E1加到Ei。
方程符合单调队列优化的标准方程： dp［i］=min{dp［j］+b［j］}+a［i］。下面用这个例子详细讲解单调优化队列的操作过程。
把i看作定值，上述方程等价于
dp［i］=max{dp［j-1］-sum［j］}+sum［i］，i-k≤j≤i
求dp［i］，就是找到一个决策j，i-k≤j≤i，使dp［j-1］-sum［j］最大。
对这个方程编程求解，如果简单地做i、j循环，复杂度为O(nk)，约为O(n2)。
如何优化？回顾单调队列优化的实质： 外层i变化时，不同的i所对应的内层j的窗口有重叠。
内层j所处理的决策dp［j-1］-sum［j］，在i变化时，确实发生了重叠。下面推理如何使用单调队列。
首先，对于一个固定的i，用一个递减的单调队列求最大的dp［j-1］-sum［j］。记ds［j］=dp［j-1］-sum［j］，并记这个i对应的最大值为dsmax［i］=max{ds［j］}。用单调队列求dsmax［i］的步骤如下。
(1) 设从j=1开始，首先让ds［1］进入队列。此时窗口内的最大值dsmax［i］=ds［1］。
(2) j=2，ds［2］进入队列，讨论两种情况。
若ds［2］≥ds［1］，说明ds［2］更优，弹走ds［1］，ds［2］进入队列成为新队头，更新dsmax［i］=ds［2］。这一步排除了不好的决策，留下更好的决策。
若ds［2］<ds［1］，ds［2］进入队列。队头仍然是ds［1］，保持dsmax［i］=ds［1］。
这两种情况下ds［2］都进入队列，是因为ds［2］比ds［1］更晚于离开窗口范围k，即存活时间更长。
(3) 继续以上操作，让窗口内的每个j(i-k≤j≤i)都有机会进入队列，并保持队列是从大到小的单调队列。
经过以上步骤，求得了固定一个i时的最大值dsmax［i］。
当i变化时，统一用一个单调队列处理，因为一个较小的i1所排除的ds［j］，在处理后面较大的i2时，也会被排除，没有必要再重新排除一次； 而且较小的i1所得到的队列，后面较大的i2也仍然有用。这样，每个ds［j］(1≤j≤n)都有机会进入队列一次，并且只进入队列一次，总复杂度为O(n)。
如果对上述解释仍有疑问，请仔细分析洛谷P2627的代码。注意一个小技巧： 虽然理论上在队列中处理的决策是dp［j-1］-sum［j］，但是在编码时不用这么麻烦，队列只需要记录j，然后在判断时用dp［j-1］-sum［j］进行计算即可。
代码中去头和去尾的两个while语句是单调队列的常用写法，可以看作单调队列的特征。
1//代码改写自https://www.luogu.com.cn/blog/user21293/solution-p2627
2#include <bits/stdc++.h>
3using namespace std;
4const int N=100005;
5long long n,k,e［N］,sum［N］,dp［N］;
6long long ds［N］;//ds［j］ = dp［j-1］-sum［j］
7int q［N］,head=0,tail=1; //递减的单调队列，队头最大
8long long que_max(int j){
9ds［j］ = dp［j-1］-sum［j］;
10while(head<=tail && ds［q［tail］］<ds［j］)tail--;//去掉不合格的队尾
11q［++tail］=j;//j进入队尾
12while(head<=tail && q［head］<j-k) head++;//去掉超过窗口k的队头
13return ds［q［head］］;//返回队头，即最大的dp［j-1］-sum［j］
14}
15int main(){
16cin >> n >> k; sum［0］ = 0;
17for(int i=1;i<=n;i++){
18cin >> e［i］;sum［i］ = sum［i-1］ + e［i］; //计算前缀和
19}
20for(int i=1;i<=n;i++) dp［i］ = que_max(i) + sum［i］; //状态转移方程
21cout << dp［n］;
22}
2. 多重背包
下面给出多重背包单调队列优化的解法，这是最优的方法。
多重背包问题： 给定n种物品和一个背包，第i种物品的体积为ci，价值为wi，并且有mi个，背包的总容量为C。如何选择装入背包的物品，使装入背包的物品的总价值最大?
回顾用滚动数组实现的多重背包代码。
//洛谷 P1776，提交判题后返回TLE
for(int i=1;i<=n;i++)//枚举每个物品
for(int j=C;j>=c［i］;j--) //枚举背包容量
for(int k=1; k<=m［i］ && k*c［i］<=j; k++)
dp［j］ = max(dp［j］,dp［j-k*c［i］］+k*w［i］);
状态转移方程为dp［j］=max{dp［j-kci］+kwi}，1≤k≤min{mi，j/ci}。
代码是i、j、k三重循环。其中，循环i、j互相独立，没有关系，不能优化； 循环j、k是相关的，k在j上有滑动窗口，所以目标是优化j、k这两层循环，此时可以把与i有关的部分看作定值。
对比单调队列的标准状态转移方程： dp［i］=max{dp［j］+a［i］+b［j］}，L(i)≤j≤R(i)，相差太大，似乎并不能应用单调队列。
回顾单调队列优化的实质，外层i变化时，不同的i所对应的内层j的窗口有重叠。状态转移方程dp［j］=max{dp［j-kci］+kwi}的外层循环是j，内层循环是k，k的滑动窗口是否重叠？下面观察j-kci的变化情况。首先对比外层j和j+1，让k从1递增，它们的j-kci如下。
j： j-3cij-2cij-ci
j+1： j+1-3cij+1-2cij+1-ci
可以看出，没有发生重叠。但是如果对比j和j+ci，发生了重叠。
j： j-3cij-2cij-ci
j+ci： j+ci-4cij+ci-3cij+ci-2ci
可以推理出，当j=j，j+ci，j+2ci，…时有重叠； 进一步推理出，当j除以ci的余数相等时，这些j对应的内层k发生重叠。那么，如果把外层j的循环改为按j除以ci的余数相等的值进行循环，就能利用单调队列优化了。
下面把原状态转移方程变换为可以应用单调队列的标准方程。原方程为
dp［j］=max{dp［j-kci］+kwi}，1≤k≤min{mi，j/ci}
令j=b+yci,其中，b=j%ci，b为j除以ci得到的余数； y=j/ci，y为j整除ci的结果。
把j代入原方程，得https://blog.csdn.net/qq_40679299/article/details/81978770
dp［b+yci］=max{dp［b+(y-k)ci］+kwi}，1≤k≤min{mi，y}
令x=y-k，代入得
dp［b+yci］=max{dp［b+xci］-xvi+ywi}，y-min(mi,y)≤x≤y
与标准方程dp［i］=min{dp［j］+a［i］+b［j］}对比，几乎一样。
用单调队列处理决策dp［b+xci］-xvi，下面给出代码，上述推理过程的原理详见代码中的注释。
1//洛谷 P1776： 单调队列优化多重背包
2#include<bits/stdc++.h>
3using namespace std;
4const int N=100010;
5int n,C;
6int dp［N］,q［N］,num［N］;
7int w,c,m;//物品的价值w，体积c，数量m
8int main(){
9cin >> n >> C;//物品数量n，背包容量C
10memset(dp,0,sizeof(dp));
11for(int i=1;i<=n;i++){
12cin>>w>>c>>m;
13if(m>C/c) m = C/c; //计算 min{m, j/c}
14for(int b=0;b<c;b++){//按余数b进行循环
15int head=1, tail=1;
16for(int y=0;y<=(C-b)/c;y++){//y = j/c
17int tmp = dp［b+y*c］-y*w;//用队列处理tmp = dp［b + xc］ - xw
18while(head<tail && q［tail-1］<=tmp) tail--;
19q［tail］ = tmp;
20num［tail++］ = y;
21while(head<tail && y-num［head］>m)head++;
22//约束条件y-min(mi,y)≤x≤y
23dp［b+y*c］ = max(dp［b+y*c］,q［head］+y*w); //计算新的dp［］
24}
25}
26}
27cout << dp［C］ << endl;
28return 0;
29}
复杂度分析： 外层i循环n次，内层的b和y循环总次数为c×(C-b)/c≈C，且每次只进出队列一次，所以总复杂度为O(nC)。
【习题】
(1) 洛谷P1725/P3957/P1776/P3089/P3572/P3522/P4544/P5665/P1973/P2569/P4852。
(2) poj 1821/2373/3017/3926。
(3) hdu 3401/3514/5945。
扫一扫
视频讲解
5.9斜率优化/凸壳优化
有一类DP状态方程：
dp［i］=min{dp［j］-a［i］d［j］}，0≤j<i，d［j］≤d［j+1］，a［i］≤a［i+1］
它的特征是存在一个既有i又有j的项a［i］d［j］，编程时，如果简单地对外层i和内层j循环，复杂度为O(n2)。
这里能用单调队列优化吗？单调队列所处理的策略，要求只能与内层j有关，与外层i无关，但是这个状态方程无法简单地得到只与j有关的部分。
用斜率(凸壳)模型，能够将方程转化，得到一个只与j有关的部分，即“斜率”，从而能够使用单调队列优化。这个算法称为斜率优化/凸壳优化(Convex Hull Trick)，总时间复杂度为O(n)，斜率优化的核心技术是斜率(凸壳)模型和单调队列。
斜率优化的数学建模在理解上有点困难，为方便读者理解，本节将详细论述算法的思想，然后用例题巩固理解，最后总结和扩展算法知识。
5.9.1把状态转移方程变换为平面的斜率问题
观察DP状态转移方程，可以把i看作不变的常量，把关于i的部分(除了dp［i］以外)看作常量，把j看作变量，目标是求j变化时dp［i］的最优值。这里难以理解的是为什么要把dp［i］看作变化的，请读完本节后再回头思考，dp［i］的变化对应了变化的直线截距。
去掉min，状态转移方程转换为
dp［j］=a［i］d［j］+dp［i］
为方便观察，令y=dp［j］，x=d［j］，k=a［i］，b=dp［i］，状态转移方程变为
y=kx+b
斜率优化的数学模型，就是把状态转移方程转换为平面坐标系直线的形式y=kx+b。
(1) 变量x、y与j有关，并且只有y中包含dp［j］。点(x，y)是题目中可能的决策。
(2) 斜率k、截距b与i有关，并且只有b中包含dp［i］。最小的b包含最小的dp［i］，也就是状态转移方程的解。
两点(x1,y1)、(x2,y2)连成的直线的斜率为(y2-y1)/(x2-x1)，它们只与j有关，这就是可以用单调队列处理的策略。
应用斜率优化的条件为x和k是单调增加的，即x随着j递增而递增，k随着i递增而递增。
5.9.2求一个dp［i］
先考虑固定i的情况下求dp［i］。由于i是定值，那么斜率k=a［i］可以看作常数。当j在0≤j<i变化时，对于某个jr，产生一个点vr=(xr，yr)，这个点在一条直线y=kx+br上，br为截距，如图5.19所示。
对于0≤j<i中所有的j，把它们对应的点都画在平面上，这些点对应的直线的斜率k=a［i］都相同，只有截距b不同。在所有这些点中，有一个点v′所在的直线有最小截距b′，计算出b′，由于b′中包含dp［i］，那么就算出了最优的dp［i］，如图5.20所示。
图5.19经过点(xr，yr)的直线
图5.20经过最优点v′的直线
如何找最优点v′？利用“下凸壳”。
前面提到，x是单调增加的，即x随着j递增而递增。图5.21(a)中给出了4个点，它们的x坐标是递增的。
图5.21用下凸壳找最优点
图5.21(a)中的点1、2、3构成了下凸壳，下凸壳的特征是线段12的斜率小于线段23的斜率。点2、3、4构成了上凸壳。经过上凸壳中间点3的直线，其截距b肯定小于经过点2或点4的有相同斜率的直线的截距，所以点3肯定不是最优点，去掉它。
去掉上凸壳后，得到图5.21(b)，留下的点都满足下凸壳关系。最优点就在下凸壳上。例如,在图5.21(c)中，用斜率为k的直线来切这些点，设线段12的斜率小于k，线段24的斜率大于k，那么点2就是下凸壳的最优点。
以上操作用单调队列编程很方便。
(1) 入队操作，队列处理的数据为斜率(y2-y1)/(x2-x1)。在队列内对这些斜率维护一个下凸壳，即每两个连续点连成的直线，其斜率是单调上升的。新的点进入队列时，确保它能与队列中的点一起仍然能够组成下凸壳。例如，队列尾部的两个点是3和4，准备进入队列的新的点是5。比较点3、4、5，看线段34和线段45的斜率是否递增，如果斜率递增，那么点3、4、5形成了下凸壳； 如果不递增，说明点4不对，从队尾弹走它； 然后继续比较队列尾部的点2、3和5； 重复以上操作，直到5能进入队列为止。经过以上操作，队列内的点组成了一个大的下凸壳，每两个连续点连成的直线斜率递增，队列保持为单调队列，如图5.22所示。
图5.22维护单调队列中的下凸壳
(2) 出队列，找到最优点。设队头的两个点是v1和v2，如果线段v1v2的斜率比k小，说明v1不是最优点，弹走它，继续比较队头新的两个点，一直到斜率大于k为止，此时队头的点就是最优点v′。
5.9.3求所有dp［i］
5.9.2节求得了一个dp［i］，复杂度为O(n)。如果对于所有i都这样求dp［i］，总复杂度仍然为O(n2)，并没有改变计算的复杂度。有优化的方法吗？
一个较小的i1，它对应的点是{v0，v1，…，vi1}； 一个较大的i2，对应了更多的点{v0，v1，…，vi1，…，vi2}，其中包含了i1的所有点。寻找i1的最优点时，需要检查{v0，v1，…，vi1}； 寻找i2的最优点时，需要检查{v0，v1，…，vi1，…，vi2}。这里做了重复的检查，并且这些重复是可以避免的。这就是能优化的地方，仍然用下凸壳进行优化。
图5.23多个i对应的直线
(1) 每个i所对应的斜率ki=a［i］是不同的，根据约束条件a［i］≤a［i+1］，当i增大时，斜率递增，如图5.23所示。
(2) 前面已经提到，对一个i1找它的最优点时，可以去掉一些点，即那些斜率比ki1小的点。这些被去掉的点，在后面更大的i2时，由于斜率ki2也更大，肯定也要被去掉。
根据上面的讨论，优化方法是对所有的i，统一用一个单调队列处理所有点； 被较小的i1去掉的点被单调队列弹走，后面更大的i2不再处理它们。
因为每个点只进入单调队列一次，总复杂度为O(n)。
下面的代码演示了以上操作。
1//q［］是单调队列，head指向队首，tail指向队尾
2//队列中的元素是斜率，用slope()函数计算两点组成的直线的斜率
3for(int i=1;i<=n;i++){
4while(head<tail && slope(q［head］,q［head+1］)<k)//队头的两点线段斜率小于k
5head++; //不合格，从队头弹出
6int j = q［head］;//队头是最优点
7dp［i］ = ...;//计算dp［i］
8while(head<tail && slope(i,q［tail-1］)<slope(q［tail-1］,q［tail］)) //入队操作
9tail--; //弹走队尾不合格的点
10q［++tail］ = i;//新的点进入队列
11}
为加深对上述代码的理解，考虑一个特例： 进入队列的点都符合下凸壳特征，且这些点连成的直线的斜率大于所有斜率ki，那么结果是队头不会被弹出，入队的点也不会被弹出，队头被重复使用n次，如图5.24所示。
图5.24一个特例
5.9.4例题
下面用一道例题给出典型代码。
例5.21Print article(hdu 3507)
问题描述： 打印一篇包含N个单词的文章，第i个单词的打印成本为Ci。在一行中打印k个单词的花费为∑ki=1Ci2+M，M为一个常数。如何安排文章，才能最小化费用？
输入： 有很多测试用例。对于每个测试用例，第1行输入两个数字N和M(0≤N≤500000，0≤M≤1000)。在接下来的第2~N+1行中，输入N个数字。输入EOF终止。
输出： 打印文章的最低费用。
题目的意思是有N个数和一个常数M，把这N个数分成若干部分，每部分的计算值为这部分数的和的平方加上M，总计算值为各部分计算值之和，求最小的总计算值。由于N很大，O(N2)的算法超时。
设dp［i］表示输出前i个单词的最小费用，DP状态转移方程为
dp［i］=min{dp［j］+(sum［i］-sum［j］)2+M}，0<j<i
其中，sum［i］表示前i个数字和。
看到这个转移方程，读者能想到它可以用斜率优化吗？虽然不可能一眼看出来，但是在阅读下面内容之前可以试试，看能不能套用y=kx+b这种斜率优化DP的标准形式，也就是把状态转移方程转换为常数k、b，以及变量x、y。
下面把DP状态转移方程改写为y=kx+b的形式。首先展开方程，得
dp［i］=dp［j］+sum［i］sum［i］+sum［j］sum［j］-2sum［i］sum［j］+M
移项得
dp［j］+sum［j］sum［j］=2sum［i］sum［j］+dp［i］-sum［i］sum［i］-M
对照y=kx+b，有
y=dp［j］+sum［j］sum［j］，y只与j有关；
x=2sum［j］，x只与j有关，且随着j递增而递增；
k=sum［i］，k只与i有关，且随着i递增而递增；
b=dp［i］-sum［i］sum［i］-M，b只与i有关，且包含dp［i］。
下面给出代码。注意一个小技巧： 虽然在理论上单调队列处理的是斜率(y(a)-y(b))/(x(a)-x(b)，但是编码时不用这样算，队列只记录a和b，判断时用(y(a)-y(b))/(x(a)-x(b)进行计算即可。细节详见代码。
1#include <bits/stdc++.h>
2using namespace std;
3const int N = 500010;
4int dp［N］;
5int q［N］;//单调队列
6int sum［N］;
7int X(int x){ return 2*sum［x］; }
8int Y(int x){ return dp［x］+sum［x］*sum［x］; }
9//double slope(int a,int b){return (Y(a)-Y(b))/(X(a)-X(b));}//除法不好，改为下面的乘法
10int slope_up(int a,int b) { return Y(a)-Y(b);} //斜率的分子部分
11int slope_down(int a,int b) { return X(a)-X(b);} //斜率的分母部分
12int main(){
13int n,m;
14while(~scanf("%d%d",&n,&m)){
15for(int i=1;i<=n;i++)scanf("%d",&sum［i］);
16sum［0］ = dp［0］ = 0;
17for(int i=1;i<=n;i++)sum［i］+=sum［i-1］;
18int head=1,tail=1;//队头/队尾
19q［tail］=0;
20for(int i=1;i<=n;i++){
21while(head<tail &&
22slope_up(q［head+1］,q［head］)<=sum［i］*slope_down(q［head+1］,
q［head］))
23 head++; //斜率小于k，从队头弹走
24int j = q［head］; //队头是最优点
25dp［i］ = dp［j］+m+(sum［i］-sum［j］)*(sum［i］-sum［j］);//计算dp［i］
26while(head<tail &&
slope_up(i,q［tail］)*slope_down(q［tail］,q［tail-1］)
<= slope_up(q［tail］,q［tail-1］)*slope_down(i,q［tail］))
27tail--;//弹走队尾不合格的点
28q［++tail］ = i; //新的点进队尾
29}
30printf("%d＼n",dp［n］);
31}
32return 0;
33}
【习题】
(1) kuangbing带你飞“专题二十斜率DP”(https://vjudge.net/article/55)。
(2) 洛谷 P2900/P3628/P3648/P4360/P5468/P2305。
(3) 洛谷P3195(玩具装箱)： DP状态转移方程为dp［i］=min{dp［j］+(sum［i］+i-sum［j］-j-L-1)2}。
(4) 洛谷P4072(征途)： 二维斜率优化，DP状态转移方程为dp［i］［p］=min{dp［j］［p-1］+(s［i］-s［j］)2}。
扫一扫
视频讲解
5.10四边形不等式优化
将四边形不等式(Quadrangle Inequality)应用于DP优化，起源于1971年Knuth的一篇论文Knuth D E. Optimum Binary Search Trees［J］. Acta Informatica，1971，1: 1425.，用来解决最优二叉搜索树问题。1980年，储枫(F.Frances Yao，姚期智的夫人)做了深入研究Yao F F. Efficient Dynamic Programming Using Quadrangle Inequalities［C］//Proceedings of the 12th Annual ACM Symposium on Theory of Computing，1980. http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p429yao.pdf.，扩展为一般性的DP优化方法，把一些DP问题复杂度从O(n3)优化到O(n2)。所以，这个方法又称为KnuthYao DP Speedup Theorem。
四边形不等式应用于DP优化的证明比较复杂，如果先给出定义和证明，会让人迷惑，所以本节按这样的顺序讲解： 先用应用场合引导出四边形不等式的概念，再进行定义和证明，最后用例题巩固。四边形不等式优化虽然理论复杂，但是编码很简单。
5.10.1应用场合
有一些常见的DP问题，通常是区间DP问题，它的状态转移方程为
dp［i］［j］=min{dp［i］［k］+dp［k+1］［j］+w［i］［j］}
其中，i≤k<j，初始值dp［i］［i］已知。min()也可以是max()。
方程的含义如下。
(1) dp［i］［j］表示从状态i到状态j的最小花费。题目一般是求dp［1］［n］，即从起点1到终点n的最小花费。
(2) dp［i］［k］+dp［k+1］［j］体现了递推关系。k在i和j之间滑动，k有一个最优值，使dp［i］［j］最小。
(3) w［i］［j］的性质非常重要。w［i］［j］是与题目有关的费用，如果它满足四边形不等式和单调性，那么计算时就能进行四边形不等式优化。
这类问题的经典的例子是“石子合并”
参考《算法竞赛入门到进阶》7.3节 “区间DP”中的石子合并问题。，在5.5节有介绍，它的状态定义就是上面的
dp［i］［j］，表示区间［i，j］上的最优值，w［i］［j］是从第i堆石子合并到第j堆石子的总数量。
在阅读后面的讲解时，读者可以对照“石子合并”这个例子来理解。注意，石子合并有多种情况和解法，详情见本节例题洛谷P1880。
重新回顾5.5节求dp［i］［j］的代码，作为后面优化代码的对照。代码中有三重循环，复杂度为O(n3)。
1for(int i=1; i<=n; i++)dp［i］［i］ = 0;//初始值
2for(int len = 2; len <= n; len++) //len为区间［i,j］的长度。从小区间扩展到大区间
3for(int i = 1; i <= n-len+1; i++){// 区间起点i
4int j = i + len - 1;// 区间终点j，i<=j<=n
5for(int k = i; k < j; k++)//大区间［i,j］从小区间［i,k］和［k+1,j］转移而来
6dp［i］［j］ = min(dp［i］［j］, dp［i］［k］ + dp［k + 1］［j］ + w［i］［j］);
7}
5.10.2四边形不等式优化操作
只需一个简单的优化操作，就能把上面代码的时间复杂度降为O(n2)。这个操作就是把循环i≤k<j改为s［i］［j-1］≤k≤s［i+1］［j］。s［i］［j］记录i~j的最优分割点，在计算dp［i］［j］的最小值时得到区间［i，j］的分割点k，记录在s［i］［j］中，用于下一次循环。
这个优化称为四边形不等式优化。下面给出优化后的代码，优化见加粗部分。
1for(i = 1;i <= n;i++){
2dp［i］［i］ = 0;
3s［i］［i］ = i;//s［］［］的初始值
4}
5for(int len = 2; len <= n; len++)
6for(int i = 1; i <= n-len+1; i++){
7int j = i + len - 1;
8for(k = s［i］［j - 1］; k <= s［i + 1］［j］; k++){ //缩小循环范围
9if(dp［i］［j］ > dp［i］［k］ + dp［k + 1］［j］ + w［i］［j］){//是否更优
10 dp［i］［j］ = dp［i］［k］ + dp［k + 1］［j］ + w［i］［j］;
11 s［i］［j］ = k; //更新最佳分割点
12}
13}
14}
代码的复杂度如何？
代码中i和k这两个循环，优化前复杂度为O(n2)。优化后，每个i内部的k的循环次数为s［i+1］［j］-s［i］［j-1］，其中j=i+len-1。那么：
i=1时，k循环s［2］［len］-s［1］［len-1］次；
i=2时，k循环s［3］［len+1］-s［2］［len］次；
…
i=n-len+1时，k循环s［n-len+2］［n］-s［n-len+1］［n+1］次。
将上述次数相加，总次数为
s［2］［len］-s［1，len-1］+s［3］［len+1］-s［2，len］+…+s［n+1,n］-s［n］［n］
=s［n-len+2］［n］-s［1］［len-1］<n
i和k循环的时间复杂度优化到了O(n)，总复杂度从O(n3)优化到了O(n2)。
在后面的四边形不等式定理证明中，将更严谨地证明复杂度。
图5.25所示为四边形不等式优化效果，s1是区间［i，j-1］的最优分割点，s2是区间［i+1，j］的最优分割点。
图5.25四边形不等式优化效果
读者对代码可能有两个疑问：
(1) 为什么能够把i≤k<j缩小到s［i］［j-1］≤k≤s［i+1］［j］？
(2) s［i］［j-1］≤s［i+1］［j］成立吗？
下面给出四边形不等式优化的正确性和复杂度的严谨证明，会解答这两个问题。
5.10.3四边形不等式定义和单调性定义
在四边形不等式DP优化中，对于费用w，有两个关键内容： 四边形不等式定义和单调性。
(1) 四边形不等式定义1： 设w是定义在整数集合上的二元函数，对于任意整数i≤
i′≤j≤j′，如果有 w(i，j)+w(i′，j′)≤w(i，j′)+w(i′，j)，则称w满足四边形不等式。
四边形不等式可以概况为： 两个交错区间的w的和小于或等于小区间与大区间的w的和。
为什么称为“四边形”？如图5.26所示，把它变成一个几何图，画成平行四边形i′ijj′。图中对角线长度和ij+i′j′大于平行线长度和ij′+i′j，这与四边形不等式的几何性质是相反的，所以可以理解成“反四边形不等式”。请读者注意，这个“四边形”只是一个帮助理解的示意图，并没有严谨的意义。图5.26这种四边形是储枫论文中的画法，也有其他的四边形画法。当中间两点i′=j时(两点重合)，四边形变成了三角形。
图5.26四边形不等式w(i，j)+w(i′，j′)≤w(i，j′)+w(i′，j)
定义1的特例是定义2。
(2) 四边形不等式定义2： 对于整数i<i+1≤j<j+1，如果有 w(i，j)+w(i+1，j+1)≤w(i，j+1)+w(i+1，j)，则称w满足四边形不等式。
定义1和定义2实际上等价，它们可以互相推导，请读者尝试证明。
(3) 单调性： 设w是定义在整数集合上的二元函数，如果对任意整数i≤i′≤j≤j′，有w(i，j′)≥w(i′，j)，称w具有单调性。
图5.27w的单调性
单调性可以形象地理解为： 如果大区间包含小区间，那么大区间的w值大于或等于小区间的w值，如图5.27所示。
在石子合并问题中，令w［i］［j］等于从第i堆石子合并到第j堆石子的石子总数，它满足四边形不等式的定义、单调性。
(1) w［i］［j］+w［i′］［j′］=w［i］［j′］+w［i′］［j］，满足四边形不等式定义。
(2) w［i］［j′］≥w［i′］［ j］，满足单调性。
利用w的四边形不等式、单调性的性质，可以推导出四边形不等式定理，用于DP优化。
5.10.4四边形不等式定理
在储枫的论文中，提出并证明了四边形不等式定理又称为KnuthYao DP Speedup Theorem，DP加速定理。。
四边形不等式定理如果w(i，j)满足四边形不等式和单调性，则用DP计算dp［］［］的时间复杂度为O(n2)。
这个定理可以通过下面两个更详细的引理证明。
引理1状态转移方程dp［i］［j］=min(dp［i］［k］+dp［k+1］［j］+w［i］［j］)，如果w［i］［j］满足四边形不等式和单调性，那么dp［i］［j］也满足四边形不等式。
引理2记s［i］［j］=k为dp［i］［j］取得最优值时的k，如果dp［i］［j］满足四边形不等式，那么有s［i］［j-1］≤s［i］［j］≤s［i+1］［j］，即s［i］［j-1］≤k≤s［i+1］［j］。
引理2直接用于DP优化，复杂度为O(n2)。
下面证明引理1、引理2、四边形不等式定理，部分内容翻译自储枫论文中对引理1和引理2的证明，并加上本书作者的解释。
定义方程：
c(i，i)=0
c(i，j)=w(i，j)+min{c(i，k-1)+c(k，j)},i<k≤j(5.1)
前面例子中的dp［i］［j］和这里的c(i，j)略有不同，dp［i］［j］=min{dp［i］［k］+dp［k+1］［j］+w［i］［j］}，其中w［i］［j］在min()内部。证明过程是一样的。
式(5.1)中的w要求满足四边形不等式和单调性，即
w(i，j)+w(i′，j′)≤w(i′，j)+w(i，j′)，i≤i′≤j≤j′
w(i′，j)≤w(i，j′)，［i′，j］［i，j′］
(5.2)
1. 证明引理1
如果w(i，j)满足四边形不等式和单调性，那么c(i，j)也满足四边形不等式，即
c(i，j)+c(i′，j′)≤c(i′，j)+c(i，j′)，i≤i′≤j≤j′(5.3)
下面证明式(5.3)。
当i=i′或j=j′时，式(5.3)显然成立，下面考虑另外两个情况： i<i′=j<j′； i<i′<j<j′。
1) i<i′=j<j′
代入式(5.3)，得到一个“反三角形不等式”，如图5.28所示的三角形ijj′，两边的和小于第3边。
c(i，j)+c(j，j′)≤c(i，j′)，i<j<j′(5.4)
现在证明式(5.4)。
假设c(i，j′)在k=z处有最小值，即c(i，j′)=cz(i，j′)。这里定义ck(i，j)=w(i，j)+c(i，k-1)+c(k，j)。
有两个对称情况： z≤j; z≥j。
z≤j时，z为(i，j′)区间的最优点，不是(i，j)区间的最优点，所以有
c(i，j)≤cz(i，j)=w(i，j)+c(i，z-1)+c(z，j)
在两边加上c(j，j′)，有
c(i，j)+c(j，j′)≤w(i，j)+c(i，z-1)+c(z，j)+c(j，j′)
≤w(i，j′)+c(i，z-1)+c(z，j′)
=c(i，j′)
图5.28引理1证明
(z≤j)图5.28和图5.29引自储枫论文。
上面的推导利用了：
(1) w的单调性，有w(i，j)≤w(i，j′)；
(2) 式(5.4)的归纳假设： 假设z≤j≤j′时成立，递推出i<j<j′时式(5.4)也成立。观察图5.28，有c(z，j)+c(j，j′)≤c(z，j′)，它满足反三角形不等式。
z≥j是上述z≤j的对称情况。
2) i<i′<j<j′
假设式(5.3)右边的小区间c(i′，j)和大区间c(i，j′)分别在k=y和k=z处有最小值，记为
c(i′，j)=cy(i′，j)
c(i，j′)=cz(i，j′)
同样有两个对称情况： z≤y； z≥y。
z≤y时，有
c(i′，j′)≤cy(i′，j′)
c(i，j)≤cz(i，j)
将两式相加，得
c(i，j)+c(i′，j′)
≤cz(i，j)+cy(i′，j′)
=w(i，j)+w(i′，j′)+c(i，z-1)+c(z，j)+c(i′，y-1)+c(y，j′)(5.5)
式(5.5)的进一步推导利用了：
(1) 根据w的四边形不等式，有w(i，j)+w(i′，j′)≤w(i′，j)+w(i，j′)；
(2) 根据式(5.3)的归纳假设，即假设z≤y<j<j′时成立。观察图5.29，有c(z，j)+c(y，j′)≤c(y，j)+c(z，j′)，满足反四边形不等式。
则式(5.5)变为
c(i，j)+c(i′，j′)
≤w(i′，j)+w(i，j′)+c(i，z-1)+c(i′，y-1)+c(y，j)+c(z，j′)
≤cy(i′，j)+cz(i，j′)
=c(i′，j)+c(i，j′)
图5.29引理1的证明
(z≤y)
z≥y是z≤y的对称情况。
引理1证毕。
2. 证明引理2
用Kc(i，j)表示max{k|ck(i，j)=c(i，j)}，也就是使c(i，j)得到最小值的那些k中，最大的那个是Kc(i，j)。定义Kc(i，i)=i。Kc(i，j)就是前面例子中的s［i］［j］。
引理2可表述为
Kc(i，j)≤Kc(i，j+1)≤Kc(i+1，j+1)(5.6)
下面证明引理2。
i=j时，显然成立。下面假设i<j。
先证明式(5.6)的第1部分Kc(i，j)≤Kc(i，j+1)。这等价于证明对于i<k≤k′≤j，有
ck′(i，j)≤ck(i，j) ck′(i，j+1)≤ck(i，j+1)(5.7)
式(5.7)的意思是如果ck′(i，j)≤ck(i，j)成立，那么ck′(i，j+1)≤ck(i，j+1)也成立。ck′(i，j)≤ck(i，j)的含义是在［i，j］区间，k′是比k更好的分割点，可以把k′看作［i，j］的最优分割点。扩展到区间［i，j+1］时，有ck′(i，j+1)≤ck(i，j+1)，即k′仍然是比k更好的分割点。也就是说，区间［i，j+1］的最优分割点肯定大于或等于k′。
下面证明式(5.7)。
根据四边形不等式，k≤k′≤j<j+1时，有
c(k，j)+c(k′，j+1)≤c(k′，j)+c(k，j+1)
两边加上 w(i，j)+w(i，j+1)+c(i，k-1)+c(i，k′-1)，得
ck(i，j)+ck′(i，j+1)≤ck′(i，j)+ck(i，j+1)
移项，得
ck′(i，j+1)≤ck′(i，j)+ck(i，j+1)-ck(i，j)(5.8)
把式(5.7)中ck′(i，j)≤ck(i，j)的两边加上ck(i，j+1)，得
ck′(i，j)+ck(i，j+1)≤ck(i，j)+ck(i，j+1)
ck′(i，j)+ck(i，j+1)-ck(i，j)≤ck(i，j+1)
结合式(5.8)，得ck′(i，j+1)≤ck(i，j+1)，式(5.7)成立。
同样可以证明，式(5.6)的右半部分Kc(i，j+1)≤Kc(i+1，j+1)，在i<i+1≤k≤k′时成立。
引理2说明当i、j增大时，Kc(i，j)是非递减的。
3. 证明四边形不等式定理
利用引理2，可推论出四边形不等式定理，即用DP计算所有的c(i，j)的时间复杂度为O(n2)。下面对这一结论进行说明。
用DP计算c(i，j)时，是按δ=j-i=0，1，2，…，n-1的间距逐步增加进行递推计算的。具体过程请回顾5.10.1节中求dp［i］［j］的代码。从c(i，j)递推到c(i，j+1)时，只需要Kc(i+1，j+1)-Kc(i，j)次最少限度的操作就够了。总次数是多少呢？对于一个固定的δ，计算所有的c(i，j)，1≤i≤n-δ，j=i+δ。
i=1时，Kc(1+1，1+δ+1)-Kc(1，δ+1)=Kc(2，δ+2)-Kc(1，δ+1)；
i=2时，Kc(2+1，2+δ+1)-Kc(2，δ+2)=Kc(3，δ+3)-Kc(2，δ+2)；
i=3时，Kc(3+1，3+δ+1)-Kc(3，δ+3)=Kc(4，δ+4)-Kc(3，δ+3)；
…
i=n-δ时，Kc(n-δ+1，n-δ+δ+1)-Kc(n-δ，δ+n-δ)=Kc(n-δ+1，n+1)-Kc(n-δ，n)。
将以上式子相加，总次数为Kc(n-δ+1，n+1)-Kc(1，δ+1)<n。
对于一个δ，计算次数为O(n)； 有n个δ，总计算复杂度为O(n2)。
以上证明了四边形不等式定理。
4. min()和max()
前面讨论的都是min()，如果是max()，也可以进行四边形不等式优化。此时四边形不等式是“反”的，即
w(i，j)+w(i′，j′)≥w(i′，j)+w(i，j′)，i≤i′≤j≤j′
定义
c(i，j)=w(i，j)+max(a(i，k)+b(k，j))，i≤k≤j
引理3若w、a、b都满足反四边形不等式，那么c也满足反四边形不等式。
引理4如果a和b满足反四边形不等式，那么
Kc(i，j)≤Kc(i，j+1)≤Kc(i+1，j+1)，i≤j
引理3和引理4的证明与引理1和引理2的证明类似。
5.10.5例题
拿到题目后，先判断w是否单调、是否满足四边形不等式，再使用四边形不等式优化DP。下面给出两道经典题。
1. 石子合并
例5.22洛谷 P1880
问题描述： 在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。
试设计一个算法，计算出将N堆石子合并成一堆的最小得分和最大得分。
输入： 第1行输入正整数N，表示有N堆石子。第2行输入N个整数，第i个整数ai表示第i堆石子的个数。
输出： 共输出两行，第1行为最小得分，第2行为最大得分。
在5.5节中，已经指出石子合并不能用贪心法，需要用DP。状态转移矩阵dp［i］［j］前文已有说明，这里不再赘述。
用四边形优化DP求解石子合并的最小值，复杂度为O(n2)。最小值用四边形不等式优化DP求解，w在四边形不等式中取等号： w［i］［j］+w［i′］［j′］=w［i］［j′］+w［i′］［j］。
本题的石子堆是环状的，转换为线形更方便处理。复制和原来一样的数据，头尾接起来，使长度为n的数列转换为长度为2n的数列，变成线性的，这是一个重要的技巧。
本题除了求石子合并的最小值，还要求最大值。虽然最大值也用DP求解，但是它不满足反四边形不等式的单调性要求，不能优化。而且也没有必要优化，可以用简单的推理得到： 区间［i，j］石子合并的最大值等于区间［i，j-1］和［i+1，j］中的石子合并最大值加w(i，j)。
石子合并问题的最优解是GarsiaWachs算法，复杂度为O(nlog2n)。参考洛谷P5569，本题N≤40000，用DP会超时。
2. 最优二叉搜索树
最优二叉搜索树是Knuth提出的经典问题，是四边形不等式优化的起源。
例5.23Optimal binary search tree(uva10304https://vjudge.net/problem/UVA10304)
问题描述： 给定有n个不同元素的集合S =(e1，e2，…，en)，有e1<e2<…<en，用S的元素建一棵二叉搜索树，希望查询频率越高的元素离根越近。访问树中元素ei的成本cost(ei)等于从根到该元素节点的路径数。给定元素的查询频率f(e1)，f(e2)，…，f(en)，定义一棵树的总成本为
f(e1)cost(e1)+f(e2)cost(e2)+…+f(en)cost(en)
总成本最低的树就是最优二叉搜索树。
输入： 输入包含多个实例，每行一个。每行以输入1≤n≤250开头，表示S的大小。在n之后
输入n个非负整数，表示元素的查询频率f(ei)，0≤f(ei)≤100。
输出： 对于输入的每个实例，打印最优二叉搜索树的总成本。
输入样例：
1 5
3 10 10 10
3 5 10 20输出样例：
0
20
20
二叉搜索树(BST)的特点是每个节点的值比它的左子树上所有节点的值大，比右子树上所有节点的值小。二叉搜索树的中序遍历
图5.30二叉搜索树
是从小到大的排列。上述第3个样例的最优二叉搜索树的形状如图5.30所示，它的总成本为5×2+10×1=20。
题目给的元素已经按照从小到大排列，可以方便地组成一棵BST。
设dp［i］［j］是区间［i，j］的元素组成的BST的最小值。把区间［i，j］分成两部分： ［i，k-1］和［k+1，j］，k在i和j之间滑动。在区间［i，j］建立的二叉树，k是根节点。这是典型的区间DP，状态转移方程为
dp［i］［j］=min{dp［i］［k-1］+dp［k+1］［j］+w(i，j)-e［k］}
其中，w(i，j)为区间和，w(i，j)=f(ei)+f(ei+1)+…+f(ej)。当把左、右子树连在根节点上时，本身的深度增加1，所以每个元素都多计算一次，这样就解决了cost(ei)的计算。最后，因为根节点k的层数是0，所以减去根节点的值e［k］。
w(i，j)符合四边形不等式优化的条件，所以dp［i］［j］可以用四边形不等式优化，算法的复杂度为O(n2)。
最优二叉搜索树问题的最优解也是GarsiaWachs算法，复杂度为O(nlog2n)。
【习题】
很多区间DP问题都能用四边形不等式优化。
(1) hdu 3516/2829/3506/3480。
(2) 洛谷P1912/P4767/P4072。
小结
DP是典型的体现计算思维的知识点，与搜索一样，是算法竞赛最常见的考点之一，每次竞赛都会出DP类型题。
本章介绍了DP的一部分常用内容，还有一些内容请读者自己了解，如：
(1) DP优化： 带权二分优化、哈希表优化、分治优化等；
(2) DP应用： 概率DP、DP 套 DP、动态DP、插头DP等。
“插头DP插头DP，陈丹琦将其翻译为Pluglike Dynamic Programming。”这个名词在中国算法竞赛选手中的流行，源于2008年信息学国家集训队陈丹琦https://www.cs.princeton.edu/~danqic/的论文《基于连通性状态压缩的动态规划问题》https://www.cs.princeton.edu/~danqic/misc/dynamicprogramming.pdf。这篇文章的关键词有状态压缩、连通性、括号表示法、轮廓线、插头、棋盘模型，都与插头DP相关，参考模板题洛谷P5056。