动态规划经典问题
目录 一、最长公共子序列O(mn) 二、最优排序二叉树O(n3) 三、最长上升子序列O(nlogn) 四、最优三角剖分O(n3) 五、最大m子段和O(mn) 六、0-1背包问题O(min{nc, 2n, n1.44n}) 七、最优排序二叉树O(n2) 八、最优合并问题O(nlogn)
一、最长公共子序列
Longest Common Subsequence(LCS)
考虑前缀x[1..i]和y[1..j]，定义c[i,j] = |LCS(x[1..i], y[1..j])|，则c[m,n] = |LCS(x, y)|. 递推公式为：
很直观， 考虑x[i]=y[j]的情形：
关键点一: 最优子结构
为了使用动态规划, 问题需具备最优子结构(Optimal Substructure)
直接书写的程序：
递归树分析：
关键点二: 重叠子问题
为了让动态规划确实发挥功效, 问题应该包含尽量多的重叠子问题(overlapping subproblems)
解决方法: 记忆化，注意memoization不是memorization
自底向上递推
空间优化
如果只需要最优值, 可以用滚动数组实现 •按照i递增的顺序计算, d[i,j]只和d[i-1,j]和d[i,j-1]以及d[i-1,j-1]有关系，因此只需要保留相邻两行, 空间复杂度为O(min{m,n}) •更进一步的, 可以只保留一行, 每次用单独的变量x保留d[i-1,j], 则递推方程为 If(i==j) d[j]=x; else { x = d[j]; d[j]=max{d[j-1], d[j]} };
变形. 回文词 •给一个字符串a, 保持原字符的顺序不变, 至少要加几个字符才能变成回文词? •例: abfcbfa->afbcfcbfa
分析 •红、绿色表示原字符, 白色为新增字符 •显然, s和s’在任何一个位置不可能都是白色(不需要加那个字符!) •应该让红色字符尽量多! 相当于求s和逆序串s’的LCS, 让LCS中的对应字符(红色)对齐, 中间的每个绿色字符都增加一个字符和它相等
二、最优排序二叉树 •给n个关键码和它们的频率，构造让期望比较次数最小的排序二叉树
分析 •定理：最优排序二叉树的子树也是最优排序二叉树 •给出关键码-频率对照表（升序排列） •问题：把哪个关键码做为根？则左右子树可以递归往下做
分析 •定理：最优排序二叉树的子树也是最优排序二叉树 •给出关键码-频率对照表（升序排列） •问题：把哪个关键码做为根？则左右子树可以递归往下做
用递归来思考，但用递推来做 •先考虑两个结点的情形
可以用矩阵来保存结果 •C[j,k]表示从j到k的关键码组成的最优排序二叉树 •Root[j,k]记录这棵排序二叉树的根
考虑三个结点的情形 •最优值放在C[B,D]中，根放在root[B,D]中
类似地，更新所有C[j-2,j]和root[j-2,j]
四个结点的情形（如A-D）
最终计算结果为
可以利用root矩阵递归地构造出最优树
时间复杂度：计算每个C[i,j]和root[i,j]需要枚举根结点，故为O(n3) 空间复杂度：需要两个n*n矩阵，O(n2)
三、最长上升子序列 最长上升子序列问题（LIS）给一个序列，求它的一个递增子序列，使它的元素个数尽量多。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7（还有其他的，这里略去）。
定义d[i]是从第1个元素到第i个元素为止的最长子序列长度, 则状态转移方程为：
直接使用这个方程得到的是O(n2)算法 下面把它优化到O(nlogn)
状态的组织
d值相同的a值只需要保留最小的, 因此用数组g[i]表示d值为i的数的a最小值, 显然 g[1]<=g[2]<=…<=g[k] 计算d[i]:需要在g中找到大于等于a[i]的第一个数j, 则d[i]=j 更新g:由于g[j]>a[i], 需要更新g[j]=a[i]
使用STL的lower_bound可以直接求出比a[i]大的第一个数, 用二分查找实现, 每次转移时间O(logn), 总时间O(nlogn)
fill(g,g+n,infinity); for(inti=0;i<n;i++)
{ intj=lower_bound(g,g+n,a[i])-g; d[i]=j+1; g[j]=a[i];
}
变形1: 航线问题
有两行点, 每行n个. 第一行点和第二行点是一一对应的, 有线连接, 如下图所示 选择尽量多的线, 两两不交叉
设与第1行第i个点对应的是第2行第f[i]个点 假设i<j, 两条线(i, f[i])和(j, f[j])的充要条件是f[i]<f[j], 因此问题变成了求f的最长上升子序列， 时间复杂度为O(nlogn)。
变形2: 两排列的LCS 给1~n的两个排列p1, p2 求p1和p2的最长公共子序列 例: 1 5 32 4 -> 5 3 42 1
分析 •算法一: 直接套用LCS算法, 时间O(n2) •算法二: 注意到把两个排列做相同的置换, LCS不变, 可以先把p1排列为1,2,3…,n 1 5324->1 2345 •即映射5->2, 2->4, 4->5, p2作同样置换 53421 ->23541 •与1,2,3..n的LCS显然是最长上升子序列, 时间降为O(nlogn)
推广: DAG上的最短路 •“上升”依赖于序关系<=, 它具有一般性 •DAG(有向无环图)的最长路径问题: 把有向边看成偏序关系, 则本题的算法一仍然适用, 时间复杂度为O(n2). 如果图的边数m比较, 可进一步优化到O(m), 因为每条边恰好考虑一次(用邻接表或前向星, 而不是邻接矩阵) •算法二不再适用!因为d值相同的a不一定可以两两相互比较, 不一定存在最小值.
四、最优三角剖分
给一个n个顶点的凸多边形, 有很多方法对它进行三角剖分(polygon triangulation) 每个三角形有一个权计算公式(如周长, 顶点权和), 求总权最小(大)的三角剖分方案
分析 •用d[i,j]表示由顶点i, i+1, …, j组成的多边形(注意i可以大于j) 的最小代价 –方案一: 枚举三个顶点, 组成一个三角形, 决策是O(n3)的 –方案二: 边(i,j)一定属于一个唯一的三角形, 设第三个顶点为k, 则决策仅为O(n) •采用方案二, 状态O(n2), 决策O(n), 总O(n3)
确定k后, 最优方案应该是d[i,k]+d[k,j]+w(i,k,j) •因此转移方程d[i,j]=max{d[i,k]+d[k,j]+w(i,k,j)}
变形1: 最优矩阵乘法链 •需要计算n个矩阵的乘积A1A2…An •由于矩阵乘法满足结合律, 可以有多种计算方法. 例如A1是10*100, A2是100*5, A3是5*50, 则 –顺序1: (A1A2)A3, 代价为10*100*5+10*5*50=7500 –顺序2: A1(A2A3), 代价为100*5*10+10*100*50=75000 •求代价最小的方案(加括号方法)
共同的结构 •用二叉树(binary tree)可以表示两个问题相同的结构, 每个结点表示一个区间(结点区间/ 矩阵区间), 左子树和右子树表示分成的两个序列 •如果在原问题中让d[i,j]表示i-1~j的最优值，则在方程形式上也完全等价
变形2. 决斗 •编号为1~n的n个人按逆时针方向排成一圈，他们要决斗n-1场。每场比赛在某相邻两人间进行，败者退出圈子，紧靠败者右边的人成为与胜者直接相邻的人。 •任意两人之间决斗的胜负都将在一矩阵中给出（如果A[i,j]=1则i与j决斗i总是赢，如果A[i,j]=0则i与j决斗时i总是输）， •求出所有可能赢得整场决斗的人的序号
五、最大m子段和 •给一个序列a1, a2, …, an •求m个不相交(可以相接)的连续序列, 总和尽量大 •例如m=2, 1 2 -3 4 5-6 7 分析 •设d[i,j]为以j项结尾的i段和的最大值, 则需要枚举此段开头y和上一段结尾x, 即 d[i,j]=max{d[i-1,x] + a[y..j]} •每次需要枚举x<y<=j, 决策量为O(n2), 状态为O(nm), 共O(n3m) •注意到如果a[j-1]也是本段的, 答案变成为d[i,j-1]+a[j], 因此方程优化为 d[i,j]=max{d[i,j-1]+a[j], d[i-1,x]+a[j]}, x<j •优化后状态仍然是二维的，但决策减少为O(n), 总O(n2m) •可以继续优化. 注意到时间主要耗费在对x的枚举上, 计算max{d[i-1,x]}. 这个值… •我们把d的第一维称为”阶段”, 则本题是典型的多阶段决策问题 –计算一个阶段时, 顺便记录本阶段最大值 –只保留相邻两个阶段(滚动数组) •则时间降为O(nm), 空间降为O(n) 六、0-1背包问题 •给定n种物品和一个背包, 物品i的重量是wi, 价值是vi, 背包容量为c •对于每个物品，要么装背包，要么不装 •选择装背包的物品集合，使得物品总重量不超过背包容量c, 且价值和尽量大 设d[i,j]为背包容量为j时, 只考虑前i个物品时的最大价值和 –如果装第i个物品, 背包容量只剩j-wi –如果不装, 背包容量不变 •因此d[i,j]=max{d[i,j-wi]+vi, d[i-1,j]} •状态有nc个, 每个状态决策只有两个, 因此总时间复杂度为O(nc). 用滚动数组后, 空间复杂度只有O(c) •当c大时, 算法效率非常低. 事实上，由于c是数值范围参数, 一般不把它看作输入规模. 这样的O(nc)只是一个伪多项式算法 •事实上, 如果物品重量和背包容量都是实数时, 算法将失败, 因为看起来物品的重量和可以是”任何实数”. •但事实是: 物品重量和只有2n种可能的取值, 并不是无限多种 •算法一: 枚举2n个子集合, 再计算, 枚举2n, 计算n, 共n2n •算法二: 采用递归枚举, 共2n •算法三: 先考虑一半元素, 保存2n/2个和. 再考虑后一半元素, 每计算出一个和w, 查找重量<=c-w的元素中价值的最大值. •前一半元素的2n/2个和按重量从小到大排序后放在表a里. 对于任何两个和i, j, 如果wi<wj且vi>vj, 则j是不需要保存的, 因此按重量排序好以后也是按价值排序的 •考虑后一半元素时, 每得到一个重量w, 用二分查找得到重量不超过c-w的最大元素, 则它的价值也最大. •预处理时间复杂度2n/2log2n/2, 每个重量w二分查找时间为log2n/2, 因此总2n/2log2n/2=O(n1.44n) 七、再谈最优排序二叉树 •给n个关键码和它们的频率，构造让期望比较次数最小的排序二叉树 基本分析 •设结点i..j的最优代价为d[i,j], 则 其中w[i,j]=fi+fi+1+…+fj,(如果认为根结点的代价为0, 则w[i,j]要减去fk).直接计算是O(n3)的•设d[i,j]的最优决策为K[i,j], 下面证明K[i,j-1]<=K[i,j]<=K[i+1,j]•从而把时间复杂度降到O(n2) 四边形不等式 •凸性(Mongecondition/quadrangle inequality) w[i,j]+w[i’j’]<=w[i’,j]+w[i,j’], i<=i’<j<=j’ •单调性(区间包含格上) w(i’,j)<=w(i,j’), i<=i’<j<=j’ 验证四边形不等式 •只需验证 w[i,j]+w[i+1,j+1]<=w[i+1,j]+w[i,j+1] •移项得 w[i+1,j+1]-w[i+1,j]<=w[i,j+1]-w[i,j] •当j固定时记函数f(x) = w[x,j+1]-w[x,j], 则上式变为: f(i+1)<=f(i), 因此 f(i)是减函数, w为凸; f(i)是增函数, w为凹 •固定i有同样的结论(减函数时为凸) 本题中的w •本题中, w的凸性更好证明: w[i,j]+w[i+1,j+1] =w[i,j]+(w[i,j]+f[j+1]-f[i]) =w[i+1,j]+w[i,j+1] •两边是完全相等的. 或者计算 f(x)=w[x,j+1]-w[x,j]=f[i+1]=常数 •常数既是增函数也是减函数, 因此 本题中, w既为凸也为凹 定理 •考虑递归式d[i,j]=min{d[i,k-1]+d[k,j]+w[i,j]} •定理(F.Yao): 若w满足四边形不等式, 则d也满足四边形不等式, 即 d[i,j]+d[i’,j’]<=d[i’,j]+d[i,j’], i<=i’<=j<=j’ •证明: 对长度i=j’-i归纳, 显然i<=1时正确. i=i’或j=j’时(同一行或同一列), 等式显然成立 –情形1:i’=j, 退化为反三角不等式 –情形2:i’<j 情形1. 反三角不等式 •i’=j时, d[i,j]+d[i’,j’]<=d[i’,j]+d[i,j’]退化为 d[i,j]+d[j,j’]<=d[i,j’] •设k为让d[i,j’]取最小值的决策(有多个时取最大的一个k, 后同). •若k<=j, 则k是计算d[i,j]考虑过的合法决策 d[i,j]<=w[i,j]+d[i,k-1]+d[k,j] •两边加上d[j,j’], 得 d[i,j]+d[j,j’]<=w[i,j]+d[i,k-1]+d[k,j]+d[j,j’] 情形2. 非退化的情形 •i’<j时, 右边保留两项d[i’,j]和d[i,j’]. 设二者取最小值时的决策分别为y和z, 仍需分z<=y和z>y两种情况(对称). 下面只考虑z<=y时 •y和z是合法决策，因此y<=j, z>i, 且 d[i,j]<=w[i,j]+d[i,z-1]+d[z,j] d[i’,j’]<=w[i’,j’]+d[i’,y-1]+d[y,j’] •两式相加并整理, 对应项写在一起, 得两式相加并整理, 对应项写在一起, 右边<= w[i,j]+w[i’,j’]+d[i,z-1]+d[i’,y-1]+d[z,j]+d[y,j’] •因z<=y, 红蓝色分别用四边形不等式, 右边<= w[i,j’]+w[i’,j]+d[i,z-1]+d[i’,y-1]+d[z,j’]+d[y,j] •按红蓝色分别组合, 得 d[i,j]+d[i’,j’]<=d[i,j’]+d[i’,j] •z<=y时命题得证. z>y时类似 决策单调性 •进一步地, d的凸性可以推出决策的单调性 •设k[i,j]为让d[i,j]取最小值的决策, 下面证明 k[i,j]<=k[i,j+1]<=k[i+1,j+1], i<=j •即: k在同行同列上都是递增的 •证明: i=j时显然成立. 由对称性, 只需证明k[i,j]<=k[i,j+1]. 记dk[i,j]=d[i,k-1]+d[k,j]+w[i,j], 则只需要证明对于所有的i<k<=k’<=j, 有 dk’[i,j]<=dk[i,j] 事实上，我们可以证明一个更强的式子dk[i,j]-dk’[i,j]<=dk[i,j+1]-dk’[i,j+1] (i<k<=k’<=j)•k’在[i,j]更优(左>=0)->k’在[i,j+1]上也更优(右>=0)•设k’是[i,j]的最优值，则对于它左边的任意k, k’在[i,j]更优可推出k’在[i,j+1]上也更优, 因此在区间[I,j+1]上, k’左边的值都比它大, 如下图 欲证dk[i,j]-dk’[i,j]<=dk[i,j+1]-dk’[i,j+1], 移项得 dk[i,j]+dk’[i,j+1]<=dk[i,j+1]+dk’[i,j] •按定义展开, 两边消去w[i,j]+w[i,j+1], 得 d[i,k-1]+d[k,j]+d[i,k’-1]+d[k’,j+1]<= d[i,k-1]+d[k,j+1]+d[i,k’-1]+d[k’,j] •同时消去红色部分，得 d[k,j]+d[k’,j+1]<=d[k,j+1]+d[k’,j] •这就是k<=k’<=j<j+1时d的凸性 算法优化 •由于k是单调, 计算d[i,j]时决策只需从k[i,j-1]枚举到k[i+1,j]即可 •当L=j-i固定时, –d[1,L+1]的决策是k[1,L]到k[2,L+1] –d[2,L+2]的决策是k[2,L+1]到k[3,L+2] –d[3,L+3]的决策是k[3,L+2]到k[4,L+3] –… –总决策是从k[1,L]到k[n-L+1,n], 共O(n) •对于O(n)个L, 共O(n2)个决策. •本题方程略有不同, 但也可用类似方法证明 八、最优合并问题 •有n个正整数, 每次可以合并两个相邻的数(相加), 代价为相加后的新数. •按如何的顺序把所有的数合并成一个, 使得代价总和尽量小? 分析 •假设数i~j的最小合并代价为d[i,j], 考虑最后一次合并, 有 d[i,j] = min{d[i,k-1]+d[k,j]+w[i,j]} •其中w[i,j] = a[i]+…+a[j] •显然w[i,j]是凸的和增的, 因此用四边形不等式优化后时间复杂度降为O(n2) •下面进一步优化到O(nlogn) 错误的贪心法 •贪心法: 每次采取代价最少的合并方案 •不一定得到最优解! 最优解为74 相容结点贪心法 •相容结点对: 中间没有原始结点的结点对 •修改的贪心法:每次合并和最小的相容结点i, j. 如果有多个, 因此让i和j尽量小 重组 •修改的贪心法没有按照题目要求合并, 得到的合并树不一定是合法的答案, 但它同样能得到了一棵树, 代价和仍然是sum{di*ai}, 其中di是叶子i的深度 •定理:用相容结点贪心法得到的树, 在保持各叶子的深度di不变的情况下可以重组成一棵满足题目要求的合并树 •算法:用修改贪心法求出深度序列, 再重组 实现上的考虑 •合并结点用圆形表示, 原始结点用正方形表示 •第i个圆形序列片段连同它左边、右边的正方形组成一个结点集合mpq(i) •每次合并的两个结点一定是某一个mpq的最小值min1(i)和次小值min2(i) •贪心过程:每次选择使min1(i)+min2(i)最小的i, 合并结点min1(i)和min2(i) 分析 •合并操作 –两个圆形: 没有影响 –一个圆形和一个正方形: 合并两个mpq –两个正方形: 三个mpq合并 算法梗概 •贪心过程: O(nlogn), 使用可并优先队列 •标记深度: O(n) •树重组: O(n)
