动态规划常见类型总结

2023年8月1日发(作者：)

动态规划常见类型总结本⽂针对动态规划的常见类型进⾏总结。虽说总结的是动态规划，但顺便把递推也放了进来。严格来说，递推不属于动态规划问题，因为动态规划不仅有递推过程，还要有决策（即取最优），但⼴义的动态规划是可以包含递推的，递推是⼀类简单的、特殊的动态规划，毕竟动态规划与递推密不可分。动态规划类型主要分为纯粹动态规划问题和复合动态规划问题。⼏点说明：1、博主本⼈于2012年对信息学竞赛中的动态规划问题进⾏了总结，最初以名为《NOIP的DP总结之DP类型》的⽂档上传⾄百度⽂库（当然题⽬难度不限于NOIP，还包括NOI甚⾄IOI级别较难的题），时隔6年，决定将该总结以博客形式发表，并且原⽂内容不进⾏改动。2、本总结中，涉及不少题⽬及其解题报告的原版照抄，但部分题⽬⽆法查证原始出处，本着以分享的⽬的写⼊总结，若有不当之处，还请包涵；若实在不妥，可请指出，本⼈尽快纠正不当之处。3、总结中涉及的不少题⽬未加描述，读者可⾃⾏百度搜索题⽬名，建议搜索关键词加上“动态规划”或“DP”。4、总结中涉及的代码为Pascal语⾔，因总结之年代久远，烦请见谅；代码是相通的，理解代码的思路即可。

⽬录

⼀、资源型主要是背包问题，背包部分的资料来源主要是《背包九讲》，另外也有⾃⼰的⼀些补充。 背包部分可以添加个叫“+-1背包”的家伙（属判定型动态规划）；其次还有机器分配类问题。01背包这个是最基础的。⾸先要注意问法，是否必须完全装满，若是，则初值除f[i,0]=0外全赋值为负⽆穷。空间优化：⼆维变⼀维，注意枚举顺序要变为downto（倒序枚举）！时间优化：内层枚举的下界取 max{V-sum{]},c[i]}相关题⽬：01背包母题，采药，poj2184，poj1882，poj1252，poj2063，poj1717，poj1203变形：1 判定性01背包：装箱问题，⽯⼦归并（装half箱），补圣⾐，挤⽜奶，积⽊城堡2 多包限制顺序型01背包：USACO Raucous Rockers（多个背包，不可以重复放物品，但放物品的顺序有限制。）F[I,j,k]表⽰决策到第i个物品、第j个背包，此背包花费了k的空间。f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]+p)

完全背包空间优化：变为⼀维。注意顺序枚举。（对应于时间优化4）时间优化（前3个其实都⽤不上，只是了解下思想）：1 若两件物品i、j满⾜c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不⽤考虑。⾸先将费⽤⼤于V的物品去掉，然后使⽤类似计数排序的做法，计算出费⽤相同的物品中价值最⾼的是哪个，可以O(V+N)地完成这个优化。这个优化⼀般作⽤较⼩，⾮常必要时再⽤。2 转化的思想（此处未优化）：将物品i拆成V/c[i]个。3 更⾼效的转化⽅法是：把第i种物品拆成费⽤为c[i]*2^k、价值为w[i]*2^k的若⼲件物品，其中k满⾜c[i]*2^k<=V。这是⼆进制的思想，因为不管最优策略选⼏件第i种物品，总可以表⽰成若⼲个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品，是⼀个很⼤的改进。4 O(nv)的⽅法：将01背包的费⽤枚举由倒序改为顺序即可。（值得⼀提的是，上⾯的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。）题⽬：完全背包母题，hdu1114，soj3664，系统可靠性

多重背包原始⽅程： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}复杂度是O(V*Σn[i])。优化：1 物品i拆分成num[i]个（复杂度不变）。2 ⼆进制拆分，将第i种物品分成若⼲件物品，其中每件物品有⼀个系数，这件物品的费⽤和价值均是原来的费⽤和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满⾜n[i]-2^k+1>0的最⼤整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。转化为了复杂度为O(V*Σlog n[i])的01背包问题。可以证明正确性。证明：若x=2^k-1，⽤1，2，4……2^(k-1)进⾏01选取可以组合1到x之间的任意⼀个数；若x=2^k-1+y,(1<=y<2^k),⽤1，2，3……2^(k-1),y进⾏01选取可以组合1到x之间的任意⼀个数，为什么呢？对于2^k<=w<=x,有w=u+y,其中必有1<=u<=2^k-1,因此u可以通过01选取组合，从⽽w可以通过01选取组合。代码：procedure MultiplePack(cost,weight,amount) if cost*amount>=V CompletePack(cost,weight) return integer k=1 while k

就是限制条件多了⼀个，变成了⼆维容量，从⽽状态多了⼀维⽽已。题⽬：hdu3236，打包（见动态规划set）poj2184

有N件物品和⼀个容量为V的背包。第i件物品的费⽤是c[i]，价值是w[i]。这些物品被划分为若⼲组，每组中的物品互相冲突，最多选⼀件。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。这个问题变成了每组物品有若⼲种策略：是选择本组的某⼀件，还是⼀件都不选。也就是说设f[k][v]表⽰前k组物品花费费⽤v能取得的最⼤权值，则有: f[k][v] =max{ f[k-1][v],f[k-1][v-c[i]]+w[i] | 物品i属于组k }使⽤⼀维数组的伪代码如下：for 所有的组k for v=V..0 for 所有的i属于组k f[v]=max{f[v],f[v-c[i]]+w[i]}注意这⾥的三层循环的顺序, “for v=V..0”这⼀层循环必须在“for 所有的i属于组k”之外。这样才能保证每⼀组内的物品最多只有⼀个会被添加到背包中。⼩优化：若两件物品i、j满⾜c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不⽤考虑。⾸先将费⽤⼤于V的物品去掉，然后使⽤类似计数排序的做法，计算出费⽤相同的物品中价值最⾼的是哪个，可以O(V+N)地完成这个优化。题⽬：hdu3033 ，hdu3449

简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表⽰若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，⼜被别的物品所依赖；另外，没有某件物品同时依赖多件物品这个问题由NOIP2006⾦明的预算⽅案⼀题扩展⽽来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若⼲主件和依赖于每个主件的⼀个附件集合组成。按照背包问题的⼀般思路，仅考虑⼀个主件和它的附件集合。可是，可⽤的策略⾮常多，包括：⼀个也不选，仅选择主件，选择主件后再选择⼀个附件，选择主件后再选择两个附件……⽆法⽤状态转移⽅程来表⽰如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）转化：考虑到所有这些策略都是互斥的（也就是说，你只能选择⼀种策略），所以⼀个主件和它的附件集合实际上对应于分组背包中的⼀个物品组，每个选择了主件⼜选择了若⼲个附件的策略对应于这个物品组中的⼀个物品，其费⽤和价值都是这个策略中的物品的值的和。但仅仅是这⼀步转化并不能给出⼀个好的算法，因为物品组中的物品还是像原问题的策略⼀样多。优化对于⼀个物品组中的物品，所有费⽤相同的物品只留⼀个价值最⼤的，不影响结果。所以，我们可以对主件i的“附件集合”先进⾏⼀次01背包，得到费⽤依次为0..V-c[i]所有这些值时相应的最⼤价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费⽤为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过⼀次01背包后，将主件i转化为V-c[i]+1个物品的物品组，就可以直接应⽤分组背包的算法解决问题了。更⼀般的问题：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有⾃⼰的附件集合，限制只是每个物品最多只依赖于⼀个物品（只有⼀个主件）且不出现循环依赖。解决这个问题仍然可以⽤将每个主件及其附件集合转化为物品组的⽅式。事实上，这是⼀种树形动态规划，其特点是每个⽗节点都需要对它的各个⼉⼦的属性进⾏⼀次动态规划以求得⾃⼰的相关属性。这已经触及到了“泛化物品”的思想。这个“依赖关系树”每⼀个⼦树都等价于⼀件泛化物品，求某节点为根的⼦树对应的泛化物品相当于求其所有⼉⼦的对应的泛化物品之和。树形转链式

题⽬：选课：有n^2做法。⾦明的预算⽅案

定义：考虑这样⼀种物品，它并没有固定的费⽤和价值，⽽是它的价值随着你分配给它的费⽤⽽变化。（详见背包九讲）

1 输出⽅案2 输出字典序最⼩的最优⽅案先逆序化，再普通动态规划。只是在输出⽅案时要注意，如果f[i][v]==f[i-1][i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成⽴，应该按照后者（即选择了物品i）来输出⽅案。3 求⽅案总数即装满背包或将背包装⾄某⼀指定容量的⽅案总数。对于这类改变问法的问题，⼀般只需将状态转移⽅程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移⽅程即为 f[i][v]=sum{ f[i-1][v], f[i][v-c[i]] }初始条件f[0][0]=1。4 求最优⽅案总数这个较简单。5 求次优解、第 K 优解维护⼀个k优解的有序序列，合并采⽤归并法可达到O(k)，故总复杂度为最优解问题的k倍。

背包问题并不是所有的都可以动态规划，有些需要搜索！1 剪枝⽅法：最优性与可⾏性2 搜索顺序的选择：性价⽐法，体积⼤的放前⾯，随机化数据（以防出题⼈坑爹）3 ⼦集和问题（以前lyp似乎出过）：⼆分+hash。4 动态规划？搜索？在看到⼀道背包问题时，应该⽤搜索还是动态规划呢？⾸先，可以从数据范围中得到命题⼈意图的线索。如果⼀个背包问题可以⽤动态规划解，V⼀定不能很⼤，否则O(VN)的算法⽆法承受，⽽⼀般的搜索解法都是仅与N有关，与V⽆关的。所以，V很⼤时（例如上百万），命题⼈的意图就应该是考察搜索。另⼀⽅⾯，N较⼤时（例如上百），命题⼈的意图就很有可能是考察动态规划了。另外，当想不出合适的动态规划算法时，就只能⽤搜索了。例如看到⼀个从未见过的背包中物品的限制条件，⽆法想出动态规划的⽅程，只好写搜索以谋求⼀定的分数了。

Inflate (+) （基本01背包）Stamps (+)(!) （对初学者有⼀定挑战性）MoneyNuggetsSubsetsRockers (+) （另⼀类有趣的“⼆维”背包问题）Milk4 (!) （很怪的背包问题问法，较难⽤纯动态规划求解）

其他：简单的⼆维动态规划+-1背包

⼆、线性动态规划何谓线性动态规划？有⼈认为是按时间复杂度来定义：复杂度由n惟⼀确定，且不能继续优化的动态规划为线性动态规划。我这⾥不做严格定义（也没找到理论的严格定义）。暂且理解为其动态规划的结构为线型的、链式的，区别于地图型（坐标型），树型，图型等。也可理解为可以从头到尾（或从尾到头）按数据列的⽣成顺序动态规划的⼀类动态规划问题。因此狭义地讲，区间动态规划也不属于线形的。典型题⽬：叠放箱⼦（？见动态规划2）、买车票、⽂字游戏、最佳加法表达式；最⼤乘积 f[i,j]=max(f[i-1,j-1]*w[j,i]) (0<=k<=n)(1=0 then f[I,j]:=Min(f[i,j],f[i-1,j-k]+time(i,k))IOI 2000 邮局问题[问题描述]按照递增顺序给出⼀条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建⽴邮局，每个村庄使⽤离它最近的那个邮局，使得所有村庄到各⾃所使⽤的邮局的距离总和最⼩。试编程计算最⼩距离和，以及邮局建⽴⽅案。思路⼀：现以f[i,j]表⽰安排前i个村庄使⽤前j个邮局，通过某种安排⼿段，使这i个村庄分别到这j个邮局中最近的⼀个的距离之和的所取到的最⼩值。 F[i,j]=min{f[k,j-1]+c[k+1,i]}(1<=ky时，建在A处更优；当xy,则邮局选址会不断往左靠，直到x=y。x

三、区间动态规划（剖分问题）⽯⼦合并变式：能量项链，多边形剖分，最少矩阵乘法次数取数游戏、加分⼆叉树

决⽃在路易⼗三和红⾐主教黎塞留当权的时代，发⽣了⼀场决⽃。N（2<=n<=500）个⼈站成⼀个圈，依次抽签。抽中的⼈和他右边的⼈决⽃，负者出圈。这场决⽃的最终结果关键取决于决⽃的顺序。现书籍任意两决⽃中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A⽐B强，B⽐C强，C⽐A强。如果A和B先决⽃，C最终会赢，但如果B和C决⽃在先，则最后A会赢。显然，他们三⼈中的第⼀场决⽃直接影响最终结果。假设现在n个⼈围成⼀个圈，按顺序编上编号1~n。⼀共进⾏n-1场决⽃。第⼀场，其中⼀⼈（设i号）和他右边的⼈（即i+1号，若i=n，其右边⼈则为1号）。负者被淘汰出圈外，由他旁边的⼈补上他的位置。已知n个⼈之间的强弱关系（即任意两个⼈之间输赢关系）。如果存在⼀种抽签⽅式使第k个⼈可能胜出，则我们说第k⼈有可能胜出，我们的任务是根据n个⼈的强弱关系，判断可能胜出的⼈数。编号为x的⼈能从所有⼈中胜出，必要条件是他能与⾃⼰“相遇”，即把环看成链，x点拆成两个在这条链的两端，中间的⼈全部被淘汰出局，x保持不败。这样，在连续⼏个⼈的链中，只须考虑头尾两个⼈能否胜利会师，中间的则不予考虑，从⽽少了⼀维状态表⽰量。设meet[i,j]记录i和j能否相遇，能相遇则为true，否则为false。状态转移⽅程为

或这这么写：F[I,j] = (f[I,k] and f[k,j]) and (e[I,k] or e[j,k]), i

【评分标准】 对于每个测试点，如果你的结果与标准答案的误差不超过0.1，则可以得到该测试点的满分，否则得0分。朴素的动态规划时间复杂度为O(L^2 · m^2 · n)，但是此题恰好可以卡过。⾸先预处理g[k][i]即把东西长度为k的区域分给南墙，分成i块的最⼩⾯积。可以轻易得出g[k][i] = g[k`][i - 1] + (k - k`)^2 * K2 (k` < k)。然后在计算f[k][i][j]即把东西长度为k的区域分给南北两边的墙，北墙分成i块，南墙分成j块的最⼩⾯积。则有：f[k][i][j] = f[k`][i - 1][j`] + g[k - k`][j - j`] (k` < k, j` < j)。 最后的答案就是f[100][m][n]。可以发现之前的⽅程具有决策单调性。也就是说，f[k][i][j]的决策k`、j`⼀定不⼩于f[k][i - 1][j]的决策k``、j``，那么每次枚举k`、j`的时候就可以从k``、j``开始枚举。这样可以把时间复杂度降到O(L^2 · m · n)。F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k)

多边形-讨论的动态规划多⾓形是⼀个单⼈玩的游戏，开始时有⼀个N个顶点的多边形。如图，这⾥N=4。每个顶点有⼀个整数标记，每条边上有⼀个“+”号或“*”号。边从1编号到N。 第⼀步，⼀条边被拿⾛；随后各步包括如下：选择⼀条边E和连接着E的两个顶点V1和 V2；得到⼀个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。最后，游戏中没有边，游戏的得分为仅剩余的⼀个顶点的值。当OP=‘+’Fmax(i,j)=max{fmax(i,k)+fmax(k+1,j)}Fmin(i,j)=min{fmin(i,k)+fmin(k+1,j)}当OP=‘*’

括号序列

⽅块消除(poj1390)Jimmy最近迷上了⼀款叫做⽅块消除的游戏. 游戏规则如下：n个带颜⾊⽅格排成⼀列，相同颜⾊的⽅块连成⼀个区域（如果两个相邻的⽅块颜⾊相同，则这两个⽅块属于同⼀个区域). 游戏时，你可以任选⼀个区域消去.设这个区域包含的⽅块数为x,则将得到x^2的分值.⽅块消去之后，右边的⽅格将向左移动.虽然游戏很简单，但是要得到⾼分也不是很容易.Jimmy希望你帮助他找出最⾼可以得到多少分.解题⽅法：f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]}ans:=f[1,m,0]

四、坐标动态规划（平⾯、地图）免费馅饼（模型转化）NOI 1998F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];

#可以忽略F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;——加单调队列优化的。

其他题⽬：⽅格取数、⼦矩阵问题、数字三⾓形、打砖块、滑雪、城堡、祝福、街道路径条数棋盘切割⼀、问题描述将⼀个８×８的棋盘进⾏如下分割：将原棋盘割下⼀块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格⼦的边进⾏)

原棋盘上每⼀格有⼀个分值，⼀块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均⽅差最⼩。均⽅差 ， 其中平均值 ， xi为第i块矩形棋盘的总分。请编程对给出的棋盘及n，求出的最⼩值。输⼊第1⾏为⼀个整数n(1

⼆、初步分析本题的实质是求⼀种最优的棋盘分割⽅式，使得每块棋盘与平均值的差值之和最⼩。⾸先我们必须明确⼏个条件（关键字），这样对我们理解题意进⽽采取正确的算法解决问题⼤有帮助：1. 均⽅差间。2. 本题提供固定的８×８棋盘，并不算⼤，这是本题有解的重要条件，并且给我们⼀个暗⽰：以棋盘格⼦为存储单位，将有很⼤的⾃由度。 于是我们开始考虑算法：对⽐⼋皇后问题的复杂度，我们不难看出这道题需要搜索更多的内容，在时间上搜索算法实不可取；因此，只能使⽤动态规划实现本题。经过分析，不难发现本题符合最优化原理：即若第i次分割为最佳分割，则第i-1次分割为且必为最佳；定义函数F[i,j][i’,j’]为[i,j]、[i’,j’]分别为左上、右下⾓的棋盘的最优值，F0[i,j][i’,j’]为[i,j]、[i’,j’]分别为左上、右下⾓的棋盘值，探寻函数F[i,j][i’,j’]的动态转移⽅程。 下⾯分析分割⽅式。当我们进⾏第i次分割时不外乎以下四种⽅式：：在实际编程的过程中，由于n是定值，实际只需求（Xi-X）的和的值作为参数，以此简化程序的计算及存储的空

逐⼀进⾏分析：（图3.4-3）横割⽅式： a、第i次切割将棋盘分为上i-1个棋盘和下1个棋盘（图（a）） A1=F0[i1,j1][i’,j2]+F[i’+1,j1][i2,j2] b、第i次切割将棋盘分为下i-1个棋盘和上1个棋盘（图（b）） A2=F[i1,j1][i’,j2]+F0[i’+1,j1][i2,j2]竖割⽅式： c、第i次切割将棋盘分为右i-1个棋盘和左1个棋盘（图（c）） A3=F[i1,j1][i2,j’]+F0[i1,j’+1][i2,j2] d、第i次切割将棋盘分为左i-1个棋盘和右1个棋盘（图（d）） A3=F0 [i1,j1][i2,j’]+F [i1,j’+1][i2,j2]状态转移⽅程为： F[i1,j1][i2,j2]=min{A1,A2,A3,A4} (1<=i1,j1<=8,i1<=i2<=8,j1<=j2<=8,2<=k<=n)其中k代表分割的棋盘数，单调递增，因此第k次分割只与k-1次的结果有关，所以每做完第k次对棋盘的规划F0ßF。由此节省下许多空间。三、程序实现 下⾯我们讨论程序实现的具体步骤与代码的优化。 ⾸先在读⼊过程段我们进⾏准备⼯作，累加计算出F0并统计出棋盘每个格⼦值之和S来计算平均数Average。s:=0;for i:=1 to 8 do

for j:=1 to 8 do begin read(f[i,j][i,j]); s

2023年8月1日发(作者：)

动态规划常见类型总结本⽂针对动态规划的常见类型进⾏总结。虽说总结的是动态规划，但顺便把递推也放了进来。严格来说，递推不属于动态规划问题，因为动态规划不仅有递推过程，还要有决策（即取最优），但⼴义的动态规划是可以包含递推的，递推是⼀类简单的、特殊的动态规划，毕竟动态规划与递推密不可分。动态规划类型主要分为纯粹动态规划问题和复合动态规划问题。⼏点说明：1、博主本⼈于2012年对信息学竞赛中的动态规划问题进⾏了总结，最初以名为《NOIP的DP总结之DP类型》的⽂档上传⾄百度⽂库（当然题⽬难度不限于NOIP，还包括NOI甚⾄IOI级别较难的题），时隔6年，决定将该总结以博客形式发表，并且原⽂内容不进⾏改动。2、本总结中，涉及不少题⽬及其解题报告的原版照抄，但部分题⽬⽆法查证原始出处，本着以分享的⽬的写⼊总结，若有不当之处，还请包涵；若实在不妥，可请指出，本⼈尽快纠正不当之处。3、总结中涉及的不少题⽬未加描述，读者可⾃⾏百度搜索题⽬名，建议搜索关键词加上“动态规划”或“DP”。4、总结中涉及的代码为Pascal语⾔，因总结之年代久远，烦请见谅；代码是相通的，理解代码的思路即可。

⽬录

⼀、资源型主要是背包问题，背包部分的资料来源主要是《背包九讲》，另外也有⾃⼰的⼀些补充。 背包部分可以添加个叫“+-1背包”的家伙（属判定型动态规划）；其次还有机器分配类问题。01背包这个是最基础的。⾸先要注意问法，是否必须完全装满，若是，则初值除f[i,0]=0外全赋值为负⽆穷。空间优化：⼆维变⼀维，注意枚举顺序要变为downto（倒序枚举）！时间优化：内层枚举的下界取 max{V-sum{]},c[i]}相关题⽬：01背包母题，采药，poj2184，poj1882，poj1252，poj2063，poj1717，poj1203变形：1 判定性01背包：装箱问题，⽯⼦归并（装half箱），补圣⾐，挤⽜奶，积⽊城堡2 多包限制顺序型01背包：USACO Raucous Rockers（多个背包，不可以重复放物品，但放物品的顺序有限制。）F[I,j,k]表⽰决策到第i个物品、第j个背包，此背包花费了k的空间。f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]+p)

完全背包空间优化：变为⼀维。注意顺序枚举。（对应于时间优化4）时间优化（前3个其实都⽤不上，只是了解下思想）：1 若两件物品i、j满⾜c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不⽤考虑。⾸先将费⽤⼤于V的物品去掉，然后使⽤类似计数排序的做法，计算出费⽤相同的物品中价值最⾼的是哪个，可以O(V+N)地完成这个优化。这个优化⼀般作⽤较⼩，⾮常必要时再⽤。2 转化的思想（此处未优化）：将物品i拆成V/c[i]个。3 更⾼效的转化⽅法是：把第i种物品拆成费⽤为c[i]*2^k、价值为w[i]*2^k的若⼲件物品，其中k满⾜c[i]*2^k<=V。这是⼆进制的思想，因为不管最优策略选⼏件第i种物品，总可以表⽰成若⼲个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品，是⼀个很⼤的改进。4 O(nv)的⽅法：将01背包的费⽤枚举由倒序改为顺序即可。（值得⼀提的是，上⾯的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。）题⽬：完全背包母题，hdu1114，soj3664，系统可靠性

多重背包原始⽅程： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}复杂度是O(V*Σn[i])。优化：1 物品i拆分成num[i]个（复杂度不变）。2 ⼆进制拆分，将第i种物品分成若⼲件物品，其中每件物品有⼀个系数，这件物品的费⽤和价值均是原来的费⽤和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满⾜n[i]-2^k+1>0的最⼤整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。转化为了复杂度为O(V*Σlog n[i])的01背包问题。可以证明正确性。证明：若x=2^k-1，⽤1，2，4……2^(k-1)进⾏01选取可以组合1到x之间的任意⼀个数；若x=2^k-1+y,(1<=y<2^k),⽤1，2，3……2^(k-1),y进⾏01选取可以组合1到x之间的任意⼀个数，为什么呢？对于2^k<=w<=x,有w=u+y,其中必有1<=u<=2^k-1,因此u可以通过01选取组合，从⽽w可以通过01选取组合。代码：procedure MultiplePack(cost,weight,amount) if cost*amount>=V CompletePack(cost,weight) return integer k=1 while k

就是限制条件多了⼀个，变成了⼆维容量，从⽽状态多了⼀维⽽已。题⽬：hdu3236，打包（见动态规划set）poj2184

有N件物品和⼀个容量为V的背包。第i件物品的费⽤是c[i]，价值是w[i]。这些物品被划分为若⼲组，每组中的物品互相冲突，最多选⼀件。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。这个问题变成了每组物品有若⼲种策略：是选择本组的某⼀件，还是⼀件都不选。也就是说设f[k][v]表⽰前k组物品花费费⽤v能取得的最⼤权值，则有: f[k][v] =max{ f[k-1][v],f[k-1][v-c[i]]+w[i] | 物品i属于组k }使⽤⼀维数组的伪代码如下：for 所有的组k for v=V..0 for 所有的i属于组k f[v]=max{f[v],f[v-c[i]]+w[i]}注意这⾥的三层循环的顺序, “for v=V..0”这⼀层循环必须在“for 所有的i属于组k”之外。这样才能保证每⼀组内的物品最多只有⼀个会被添加到背包中。⼩优化：若两件物品i、j满⾜c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不⽤考虑。⾸先将费⽤⼤于V的物品去掉，然后使⽤类似计数排序的做法，计算出费⽤相同的物品中价值最⾼的是哪个，可以O(V+N)地完成这个优化。题⽬：hdu3033 ，hdu3449

简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表⽰若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，⼜被别的物品所依赖；另外，没有某件物品同时依赖多件物品这个问题由NOIP2006⾦明的预算⽅案⼀题扩展⽽来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若⼲主件和依赖于每个主件的⼀个附件集合组成。按照背包问题的⼀般思路，仅考虑⼀个主件和它的附件集合。可是，可⽤的策略⾮常多，包括：⼀个也不选，仅选择主件，选择主件后再选择⼀个附件，选择主件后再选择两个附件……⽆法⽤状态转移⽅程来表⽰如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）转化：考虑到所有这些策略都是互斥的（也就是说，你只能选择⼀种策略），所以⼀个主件和它的附件集合实际上对应于分组背包中的⼀个物品组，每个选择了主件⼜选择了若⼲个附件的策略对应于这个物品组中的⼀个物品，其费⽤和价值都是这个策略中的物品的值的和。但仅仅是这⼀步转化并不能给出⼀个好的算法，因为物品组中的物品还是像原问题的策略⼀样多。优化对于⼀个物品组中的物品，所有费⽤相同的物品只留⼀个价值最⼤的，不影响结果。所以，我们可以对主件i的“附件集合”先进⾏⼀次01背包，得到费⽤依次为0..V-c[i]所有这些值时相应的最⼤价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费⽤为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过⼀次01背包后，将主件i转化为V-c[i]+1个物品的物品组，就可以直接应⽤分组背包的算法解决问题了。更⼀般的问题：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有⾃⼰的附件集合，限制只是每个物品最多只依赖于⼀个物品（只有⼀个主件）且不出现循环依赖。解决这个问题仍然可以⽤将每个主件及其附件集合转化为物品组的⽅式。事实上，这是⼀种树形动态规划，其特点是每个⽗节点都需要对它的各个⼉⼦的属性进⾏⼀次动态规划以求得⾃⼰的相关属性。这已经触及到了“泛化物品”的思想。这个“依赖关系树”每⼀个⼦树都等价于⼀件泛化物品，求某节点为根的⼦树对应的泛化物品相当于求其所有⼉⼦的对应的泛化物品之和。树形转链式

题⽬：选课：有n^2做法。⾦明的预算⽅案

定义：考虑这样⼀种物品，它并没有固定的费⽤和价值，⽽是它的价值随着你分配给它的费⽤⽽变化。（详见背包九讲）

1 输出⽅案2 输出字典序最⼩的最优⽅案先逆序化，再普通动态规划。只是在输出⽅案时要注意，如果f[i][v]==f[i-1][i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成⽴，应该按照后者（即选择了物品i）来输出⽅案。3 求⽅案总数即装满背包或将背包装⾄某⼀指定容量的⽅案总数。对于这类改变问法的问题，⼀般只需将状态转移⽅程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移⽅程即为 f[i][v]=sum{ f[i-1][v], f[i][v-c[i]] }初始条件f[0][0]=1。4 求最优⽅案总数这个较简单。5 求次优解、第 K 优解维护⼀个k优解的有序序列，合并采⽤归并法可达到O(k)，故总复杂度为最优解问题的k倍。

背包问题并不是所有的都可以动态规划，有些需要搜索！1 剪枝⽅法：最优性与可⾏性2 搜索顺序的选择：性价⽐法，体积⼤的放前⾯，随机化数据（以防出题⼈坑爹）3 ⼦集和问题（以前lyp似乎出过）：⼆分+hash。4 动态规划？搜索？在看到⼀道背包问题时，应该⽤搜索还是动态规划呢？⾸先，可以从数据范围中得到命题⼈意图的线索。如果⼀个背包问题可以⽤动态规划解，V⼀定不能很⼤，否则O(VN)的算法⽆法承受，⽽⼀般的搜索解法都是仅与N有关，与V⽆关的。所以，V很⼤时（例如上百万），命题⼈的意图就应该是考察搜索。另⼀⽅⾯，N较⼤时（例如上百），命题⼈的意图就很有可能是考察动态规划了。另外，当想不出合适的动态规划算法时，就只能⽤搜索了。例如看到⼀个从未见过的背包中物品的限制条件，⽆法想出动态规划的⽅程，只好写搜索以谋求⼀定的分数了。

Inflate (+) （基本01背包）Stamps (+)(!) （对初学者有⼀定挑战性）MoneyNuggetsSubsetsRockers (+) （另⼀类有趣的“⼆维”背包问题）Milk4 (!) （很怪的背包问题问法，较难⽤纯动态规划求解）

其他：简单的⼆维动态规划+-1背包

⼆、线性动态规划何谓线性动态规划？有⼈认为是按时间复杂度来定义：复杂度由n惟⼀确定，且不能继续优化的动态规划为线性动态规划。我这⾥不做严格定义（也没找到理论的严格定义）。暂且理解为其动态规划的结构为线型的、链式的，区别于地图型（坐标型），树型，图型等。也可理解为可以从头到尾（或从尾到头）按数据列的⽣成顺序动态规划的⼀类动态规划问题。因此狭义地讲，区间动态规划也不属于线形的。典型题⽬：叠放箱⼦（？见动态规划2）、买车票、⽂字游戏、最佳加法表达式；最⼤乘积 f[i,j]=max(f[i-1,j-1]*w[j,i]) (0<=k<=n)(1=0 then f[I,j]:=Min(f[i,j],f[i-1,j-k]+time(i,k))IOI 2000 邮局问题[问题描述]按照递增顺序给出⼀条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建⽴邮局，每个村庄使⽤离它最近的那个邮局，使得所有村庄到各⾃所使⽤的邮局的距离总和最⼩。试编程计算最⼩距离和，以及邮局建⽴⽅案。思路⼀：现以f[i,j]表⽰安排前i个村庄使⽤前j个邮局，通过某种安排⼿段，使这i个村庄分别到这j个邮局中最近的⼀个的距离之和的所取到的最⼩值。 F[i,j]=min{f[k,j-1]+c[k+1,i]}(1<=ky时，建在A处更优；当xy,则邮局选址会不断往左靠，直到x=y。x

三、区间动态规划（剖分问题）⽯⼦合并变式：能量项链，多边形剖分，最少矩阵乘法次数取数游戏、加分⼆叉树

决⽃在路易⼗三和红⾐主教黎塞留当权的时代，发⽣了⼀场决⽃。N（2<=n<=500）个⼈站成⼀个圈，依次抽签。抽中的⼈和他右边的⼈决⽃，负者出圈。这场决⽃的最终结果关键取决于决⽃的顺序。现书籍任意两决⽃中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A⽐B强，B⽐C强，C⽐A强。如果A和B先决⽃，C最终会赢，但如果B和C决⽃在先，则最后A会赢。显然，他们三⼈中的第⼀场决⽃直接影响最终结果。假设现在n个⼈围成⼀个圈，按顺序编上编号1~n。⼀共进⾏n-1场决⽃。第⼀场，其中⼀⼈（设i号）和他右边的⼈（即i+1号，若i=n，其右边⼈则为1号）。负者被淘汰出圈外，由他旁边的⼈补上他的位置。已知n个⼈之间的强弱关系（即任意两个⼈之间输赢关系）。如果存在⼀种抽签⽅式使第k个⼈可能胜出，则我们说第k⼈有可能胜出，我们的任务是根据n个⼈的强弱关系，判断可能胜出的⼈数。编号为x的⼈能从所有⼈中胜出，必要条件是他能与⾃⼰“相遇”，即把环看成链，x点拆成两个在这条链的两端，中间的⼈全部被淘汰出局，x保持不败。这样，在连续⼏个⼈的链中，只须考虑头尾两个⼈能否胜利会师，中间的则不予考虑，从⽽少了⼀维状态表⽰量。设meet[i,j]记录i和j能否相遇，能相遇则为true，否则为false。状态转移⽅程为

或这这么写：F[I,j] = (f[I,k] and f[k,j]) and (e[I,k] or e[j,k]), i

【评分标准】 对于每个测试点，如果你的结果与标准答案的误差不超过0.1，则可以得到该测试点的满分，否则得0分。朴素的动态规划时间复杂度为O(L^2 · m^2 · n)，但是此题恰好可以卡过。⾸先预处理g[k][i]即把东西长度为k的区域分给南墙，分成i块的最⼩⾯积。可以轻易得出g[k][i] = g[k`][i - 1] + (k - k`)^2 * K2 (k` < k)。然后在计算f[k][i][j]即把东西长度为k的区域分给南北两边的墙，北墙分成i块，南墙分成j块的最⼩⾯积。则有：f[k][i][j] = f[k`][i - 1][j`] + g[k - k`][j - j`] (k` < k, j` < j)。 最后的答案就是f[100][m][n]。可以发现之前的⽅程具有决策单调性。也就是说，f[k][i][j]的决策k`、j`⼀定不⼩于f[k][i - 1][j]的决策k``、j``，那么每次枚举k`、j`的时候就可以从k``、j``开始枚举。这样可以把时间复杂度降到O(L^2 · m · n)。F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k)

多边形-讨论的动态规划多⾓形是⼀个单⼈玩的游戏，开始时有⼀个N个顶点的多边形。如图，这⾥N=4。每个顶点有⼀个整数标记，每条边上有⼀个“+”号或“*”号。边从1编号到N。 第⼀步，⼀条边被拿⾛；随后各步包括如下：选择⼀条边E和连接着E的两个顶点V1和 V2；得到⼀个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。最后，游戏中没有边，游戏的得分为仅剩余的⼀个顶点的值。当OP=‘+’Fmax(i,j)=max{fmax(i,k)+fmax(k+1,j)}Fmin(i,j)=min{fmin(i,k)+fmin(k+1,j)}当OP=‘*’

括号序列

⽅块消除(poj1390)Jimmy最近迷上了⼀款叫做⽅块消除的游戏. 游戏规则如下：n个带颜⾊⽅格排成⼀列，相同颜⾊的⽅块连成⼀个区域（如果两个相邻的⽅块颜⾊相同，则这两个⽅块属于同⼀个区域). 游戏时，你可以任选⼀个区域消去.设这个区域包含的⽅块数为x,则将得到x^2的分值.⽅块消去之后，右边的⽅格将向左移动.虽然游戏很简单，但是要得到⾼分也不是很容易.Jimmy希望你帮助他找出最⾼可以得到多少分.解题⽅法：f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]}ans:=f[1,m,0]

四、坐标动态规划（平⾯、地图）免费馅饼（模型转化）NOI 1998F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];

#可以忽略F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;——加单调队列优化的。

其他题⽬：⽅格取数、⼦矩阵问题、数字三⾓形、打砖块、滑雪、城堡、祝福、街道路径条数棋盘切割⼀、问题描述将⼀个８×８的棋盘进⾏如下分割：将原棋盘割下⼀块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格⼦的边进⾏)

原棋盘上每⼀格有⼀个分值，⼀块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均⽅差最⼩。均⽅差 ， 其中平均值 ， xi为第i块矩形棋盘的总分。请编程对给出的棋盘及n，求出的最⼩值。输⼊第1⾏为⼀个整数n(1

⼆、初步分析本题的实质是求⼀种最优的棋盘分割⽅式，使得每块棋盘与平均值的差值之和最⼩。⾸先我们必须明确⼏个条件（关键字），这样对我们理解题意进⽽采取正确的算法解决问题⼤有帮助：1. 均⽅差间。2. 本题提供固定的８×８棋盘，并不算⼤，这是本题有解的重要条件，并且给我们⼀个暗⽰：以棋盘格⼦为存储单位，将有很⼤的⾃由度。 于是我们开始考虑算法：对⽐⼋皇后问题的复杂度，我们不难看出这道题需要搜索更多的内容，在时间上搜索算法实不可取；因此，只能使⽤动态规划实现本题。经过分析，不难发现本题符合最优化原理：即若第i次分割为最佳分割，则第i-1次分割为且必为最佳；定义函数F[i,j][i’,j’]为[i,j]、[i’,j’]分别为左上、右下⾓的棋盘的最优值，F0[i,j][i’,j’]为[i,j]、[i’,j’]分别为左上、右下⾓的棋盘值，探寻函数F[i,j][i’,j’]的动态转移⽅程。 下⾯分析分割⽅式。当我们进⾏第i次分割时不外乎以下四种⽅式：：在实际编程的过程中，由于n是定值，实际只需求（Xi-X）的和的值作为参数，以此简化程序的计算及存储的空

逐⼀进⾏分析：（图3.4-3）横割⽅式： a、第i次切割将棋盘分为上i-1个棋盘和下1个棋盘（图（a）） A1=F0[i1,j1][i’,j2]+F[i’+1,j1][i2,j2] b、第i次切割将棋盘分为下i-1个棋盘和上1个棋盘（图（b）） A2=F[i1,j1][i’,j2]+F0[i’+1,j1][i2,j2]竖割⽅式： c、第i次切割将棋盘分为右i-1个棋盘和左1个棋盘（图（c）） A3=F[i1,j1][i2,j’]+F0[i1,j’+1][i2,j2] d、第i次切割将棋盘分为左i-1个棋盘和右1个棋盘（图（d）） A3=F0 [i1,j1][i2,j’]+F [i1,j’+1][i2,j2]状态转移⽅程为： F[i1,j1][i2,j2]=min{A1,A2,A3,A4} (1<=i1,j1<=8,i1<=i2<=8,j1<=j2<=8,2<=k<=n)其中k代表分割的棋盘数，单调递增，因此第k次分割只与k-1次的结果有关，所以每做完第k次对棋盘的规划F0ßF。由此节省下许多空间。三、程序实现 下⾯我们讨论程序实现的具体步骤与代码的优化。 ⾸先在读⼊过程段我们进⾏准备⼯作，累加计算出F0并统计出棋盘每个格⼦值之和S来计算平均数Average。s:=0;for i:=1 to 8 do

for j:=1 to 8 do begin read(f[i,j][i,j]); s