动态规划的分类解析

1、动态规划,动态规划,什么是动态规划 动态规划的条件 动态规划的关键 几种常见动态规划的种类 例题分析,什么是动态规划,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,由此不难得出结论：动态规划实质就是,记忆化搜索,下面这个数塔的例子将形象地向我们展示这样的结论 给你一个数字三角形, 形式如下: 1 2 3 8 5 18 14 2 1

2、 10 找出从第一层到最后一层的一条 路,使得所经过的权值之和最小或 者最大.,当然，大家都很清楚的知道转移方程为optij=maxopti-1 j, opti-1j-1 +aij，边界条件特殊处理即可。 但只要仔细想想就会发现，这不过是一个加了强力剪枝的记忆化搜索而已，因为每个点我们只记录到当前节点的最优解，因此省去了大量的重复计数和明显不是最优解的情况，从而使运行速度有了极大的优化,动态规划的条件,而在求解的过程中一道能使用动规解决的题必须具备以下几个条件 无后效性,即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一

3、个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。 满足最优子结构性质，即一个问题的最优解必须是在子问题取得最优解的情况下决策出来的,动态规划的过程可以简单地描述为,找出最优解的性质，并刻画其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,动态规划的关键,有明确的状态 状态转移方程清晰正确,几种常见动规的种类,线性动规 背包问题,区间动规 树形动规,下面让我们通过几个例子来 了解这些基本动规的思考方法,拦截导弹（Noip2002）,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第

4、一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。 某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。,状态的确定,状态的表示fi，表示当第i个导弹必须拦截时，前i个导弹中最多能拦截多少。 每个导弹有一定的高度，当前状态就是以第i个导弹为最后一个拦截的导弹。以前状态就是在这个导弹之前拦截的那个导弹。 对于fi，我们考察在i之前位置的导弹，找到所有可以连接上的导弹k（即满足其高度大于等于第i个导弹），选择其中fk值最大的一个，fi=fk+1；如果没有满足条件的k，则f

5、i=1。 这是线性动态规划的经典例题。,代码,for (int i = 1; i = ai) mx = max(mx, fj + 1); fi = mx; int ans = 0; for (int i = 1; i = n; i+) ans = max(ans, fi); printf(%dn, ans);,最低通行费,一个商人穿过一个 N*N 的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。 这个商人期望在规定时间内用最少费用

6、穿越出去。请问至少需要多少费用？ 注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。,最低通行费,输入 第一行是一个整数，表示正方形的宽度N (1 = N 100)； 后面 N 行，每行 N 个不大于 100 的整数，为网格上每个小方格的费用。 输出 至少需要的费用。,分析,这个问题的关键在于发现对移动方向的限制：即由于必须在(2N-1)单位时间内完成移动，因此仅能向下或者向右移动。 当移动方向限定后，不难看出这个问题就是变形的数塔问题，于是可以借助动态规划高效解决。,状态的确定,我们用optij表示从左上角入口移动到第i行j列的最小代价。 则opti,j=mino

7、pti-1j, optij-1) + aij; 最后输出optnn;,代码,for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) scanf(“%d”, ,乘积最大,国际数学联盟确定的“2000世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛活动，你的好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N(N40)的数字串，要求选手使用M(M6)个乘号将它分成M+1个部分，找出一种分法，使得这M+1个部分的乘积最大。 同时，为了帮

8、助选手能够理解题意，主持人还举了如下一个例子： 有一个数字串：312，当N=3，M=1时会有两种分法： 312=36 312=62 这时，符合题目要求的结果是：312=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。,分析,由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。显然，运算任何整数类型都无法容纳如此之大的数据，只能采用高精度运算，限于篇幅，对于高精度的加法运算、乘法运算和比较大小的运算，这里不作介绍，只是对的乘号最佳插入方式进行探讨： 假设s1si(2in)中插入j个乘号，其中s1sk中插入了j-1个乘号，即乘式中的第j+1项为sk+1s

9、i(jki-1)：,分析,设 ansij长度为i的数串中插入j个乘号的最大乘积（整型数组）。显然 ansi0=s1.si对应的整型数组； ansij=maxanskj-1sk+1.si （1in， 1jmini-1,m，jki-1） ansnm即为其解。,分析,由于乘式中第j+1项sk+1si为常量，因此要使得ansij最大，则s1sk中插入j-1个乘号的乘积必须最大；同样，为了寻找第j个乘号的最佳插入位置，必须一一查阅子问题ansjj-1ansi-1j-1的解。显然该问题具备无后效性、最优子结构的特征，适用于动态规划方法。,状态的确定,我们用ansij表示前i个字符插入j个乘号可以获得的最大

10、值 则有： ansi0=s1.si ansij = maxanskj-1sk+1.si (jki-1) ansnm即为其解。,代码,输入n，m和数串s； for i1 to n do ansi0s1.si对应的整数数组； for i2 to n do 阶段：枚举数串的长度 for j1 to mini-1,m do 状态：枚举长度为i的数串中插入的乘号个数 for kj to i-1 do 决策：枚举第j个乘号的插入位置 begin nextsk+1.si对应的整数数组； 计算第j+1项 ansijmaxansij， anskj-1next； 计算状态转移方程 end；for 输出最大乘积an

11、snm；,过河,在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。,分析,从正面来考虑的

12、话，这个问题是一个搜索性的问题，需要考虑从当前点出发可以跳到的所有点。 然而从反面考虑的话，我们只需要考虑那些能到用一步到达当前点的所有点中，踩到石头数最小的那个。 即opti=minoptk (max0,i-tki-s)+brii;,代码,For i1 to n do opti=10000000; opt0=0; For is to L+t do for kmax0,i-t to i-s do if (optk+briiopti) opti=optk+brii;,以上都是线性动规的一些例题，它们的基础时间复杂度都是O(N2),装箱问题,有一个箱子容量为maxv(正整数，maxv20000)，

13、同时有n件物品(0n30)，每件物品有一个体积vi(正整数) 。要求从这n件物品中任取若干件装入箱内，使箱子的剩余空间最小。,分析,这是一个最基础的背包问题，只需要考虑选取哪几个物品放入箱子，可以使得剩余体积最小。 这道题的基本做法当然还是穷举放进背包的物品编号。若我们把取该物品记为1，不取该物品记为0，那么使用某种放入方式将对应一个2进制串，因此这类问题也被称为0-1背包问题. 如果我们不从物品角度考虑，而是从体积角度考虑的话，就会发现，这个问题还可以被描述为，wi的体积是否能由这些物品得到。,状态的确定,我们用optij（布尔）表示前i个物品是否能达到j体积。则optij的值取决于前i-1

14、个物品能否达到j体积，或者是前i-1个物品能否达到j-vi体积 则有optij=(opti-1j-vi)or(opti-1j) 初值为opt00=true；其他都为false,代码,memset(opt, 0, sizeof(opt); opt00 = 1; for (int i = 1; i = vi) optij = opti - 1j | opti - 1j - vi; else optij = opti - 1j;,采药,辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山

15、洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 输入的第一行有两个整数T(1T1000)和N(1N100)，用一个空格隔开，T代表总共能够用来采药的时间，N代表山洞里的草药的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。,分析,和上面一个问题一样，这个问题同样可以采用搜索解决，然而搜索的时间复杂度也同样相当的可怕。 那我们可不可以借鉴一下上面的想法来解决这个问题呢

16、？,状态的确定,答案是肯定的。 类似地，我们用optij表示前i个物体在j时间内的一个参数。但是我们在里面存的值并不是能否达到，而是在这个状态下可以达到的最大价值。 但是状态的转移方程稍微有些差别，除了考虑opti-1j-ti和opti-1j之外，还要考虑optij-1 (这样可以最后直接输出optnmaxt从而省掉一次扫描)，即optij表示前i个物体在j时间内可以达到的最大价值，注意这里包括不足j时间的情况。,代码,memset(opt, 0, sizeof(opt); opt00 = 0; for (int i = 1; i = vi) optij = maxopti-1j, opti-

17、1j-ti+valuei, optij-1 else optij = maxopti-1j, optij-1; printf(%dn, optnmaxt);,Dairy Queen,奶牛Bassie去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬币面值为ai 。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1=total=1000,1=n=1000,1=ai=300) 求一共有多少种解决方案？ 【输入】 第一行为硬币总值total和硬币种

18、类数n。 以下n行为数值ai，i=1,2,3.n 【输出】 一行，解决方案数,分析,这道题目和上面的采药的区别仅仅在于，每个物品可以无限次的取。 当然，这样的问题仍然可以用背包模型来解决，我们将这种模型称为无限背包。 在这种情况下，我们只要把opti-1j-ai改成optij-ai,即允许一种物品被取多次。 由于是计数，所以optij=optij-ai+opti-1j。 一个重要的优化：我们可以把opt数组压缩成长度为total的一维数组，因为这样是不会影响结果的，但可以大大降低它的空间复杂度。,状态的确定,我们用optj表示硬币总面值为j时共有多少种方法 optj=optj+optj-ai

19、(i=1,2,3.n),代码,memset(opt, 0, sizeof(opt); opt0 = 1; for (int i = 1; i = n; i+) for (int j = ai; j = total; j+) optj = optj + optj - ai; printf(%dn, opttotal);,多重背包,问题题目 有N种物品和一个容量为V的背包。第i种物品最多有mi件可用，每件体积是vi，价值是wi。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。 输入样例 100 3 maxv,n 70 40 20 v1,v2,vn 50 40 30 w1

20、,w2,wn 1 2 3 m1,m2,m3,mn,分析,本题和无限背包问题很类似。基本的方程只需将无限背包问题的方程略微一改即可，因为对于第i种物品有mi+1种策略：取0件，取1件取 mi件。令fiv表示前i种物品恰放入一个容量为v的背包的最大价值，则：fiv=maxfi-1v-kvi+ kwi | 0= t) k+; v1k = vi * t; w1k = wi * t; mi = mi - t; t best) best = optj; printf(%dn, best);,代码,以上都是背包问题的一些例题，他们的基础时间复杂度都是O(mn)的,最小代价子母树,问题描述： 有n堆沙子排成一

21、排，每堆沙子有一个数量，例如：13 7 8 16 21 4 18。任意2堆相邻的沙子可以进行合并，将两堆沙子合并为一堆时，两堆沙子数量的和称为合并这两堆沙子的代价。经过不断的归并，最后将这些沙子归为一堆，而全部归并代价的和称为总代价。例如上列数，其中2种归并方案的代价为： 第1种的总代价为 20+24+25+44+69+87 = 267 第2种的总代价为 15+37+22+28+59+87 = 248 由此可见，不同的归并过程得到的总代价是不一样的。 问题：当n个数给出后，找出一种合理的归并方法，使得总代价最小。,分析,（1）如果把归并14堆看成整个问题，则这个问题可以分解为三个归并方案，每个

22、归并方案包含12个子问题： 先归并13；再与4归并 归并12，归并34；再归并 归并24；再与1归并 （2） 如果我们继续分析增加更多堆数进行归并的问题，就会发现n个数归并时，会分解为n-1种类型： Case1: 归并第1堆，归并2n堆；再最后归并 Case2: 归并12堆，归并3n堆；再最后归并 Case n-1: 归并1n-1堆，归并第n堆；再最后归并,分析,通过前面的分析，我们看到，归并代价实际上由两部分组成： （1）归并树左右子树的最小代价之和 （2）归并树所有叶结点的权值之和 而对于opt数组中的子区间数值的取值大小， 我们有两种渠道来获取： （1）利用普通的dp，枚举开始结点和区间

23、长度来进行DP （2）记忆化搜索,状态的确定,我们用opti,j表示i-j区间合并成一堆的最小代价，则有上面的结论有 optij=minoptik+optk+1j(k=i.j-1)+valuei.j; optii=valuei;,代码,for (int i = 1; i optik+optk+1i+j-1+vi+j-1-vi-1) optii+j-1=optik+optk+1i+j-1+vi+j-1-vi-1; printf(%dn, opt1n);,Power,多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。 多瑞卡每晚到早晨5点钟

24、都在晚会上，然后他开始关灯。开始时，他站在某一盏路灯的旁边。 每盏灯都有一个给定功率的电灯泡，因为多端卡有着自觉的节能意识，他希望在耗能总数最少的情况下将所有的灯关掉。 多端卡因为太累了，所以只能以1m/s的速度行走。关灯不需要花费额外的时间，因为当他通过时就能将灯关掉。 编写程序，计算在给定路灯位置，灯泡功率以及多瑞卡的起始位置的情况下关掉所有的灯的最少耗能。,Power,输入 第一行包含一个整数N，2N1000，表示该村庄路灯的数量。 第二行包含一个整数V，1VN，表示多瑞卡开始关灯的路灯号码。 接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数，其中0D,W1000

25、。D表示该路灯与村庄开始处的距离(用米为单位来表示)，W表示灯泡的功率，每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。 输出 一行，包含一个整数，即消耗能量之和的最小值。注意结果不超过1,000,000,000。,分析,首先，我们必须明确这样一个决策：我们关掉的灯必然是一个连续的区间，也就是说，我们在路过的时候肯定会把灯顺手关掉，不然肯定不是最优解。 而在关掉一个区间之后，我们需要作出的决定就是，回头关另外一边的灯还是继续朝当前方向走关前面的灯。 对于我们的最后求解区间i.j,有2种可能：最后关第j盏灯，或者最后关第i盏灯。,分析,为了实现对这两种情况的记录，我们需要两个数组，分别存放关完i

26、,j区间的所有路灯后分别站在两个端点时最小的电能消耗值。 并且这两个数组中，kgdje（k=1.2.3.gdje-1）区间的数值和gdjek(k=gdje+1.n)区间的数值都是很容易确定的(gdje为开始位置)。 在下面的动规过程中，我们只需要决策是需要转向另外一边还是继续走下去就可以了。,状态的确定,我们用leftij表示关完灯后人站在i点所消耗的最小电能，用rightij表示关完灯后人站在j点所消耗的最小电能，则有 leftij=min lefti+lj+(value1.i+valuej+1.n)*(posi+1-posi), righti+lj+(value1i+valuej+1.n)

27、*(posj-posi); rightij=min leftij-1+(value1.i-1+valuej.n)*(posj-posi), rightij-1+(value1.i-1+valuej.n)*(posj-posj-1),加分二叉树,设一个n个节点的二叉树tree的中序遍历为(l,2,3,n)，其中数字1,2,3,n为节点编号。每个节点都有一个分数(均为正整数)，记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree(也包含tree本身)的加分计算方法如下： (subtree的左子树的加分)(subtree的右子树的加分)subtree的根的分数 若某

28、个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为(1,2,3,n)且加分最高的二叉树tree。要求输出； (1)tree的最高加分 (2)tree的前序遍历,加分二叉树,【输入格式】 第1行：一个整数n(n30)，为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数(分数100) 【输出格式】 第1行：一个整数，为最高加分(结果不会超过4,000,000,000)。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 输出样例 145 3 1 2 4 5,分析,我们可以发现这道题目给我们提供了一

29、段序列，我们需要做的就是每次选取一个断开的点，然后把问题递归地求解就可以了。 这就为我们的动规提供了条件：具有最优子结构性质。 我们需要做出的决策，仅仅是从当前序列中选取一个点作为当前子树的根节点，所以动规的转移是O(n)的。,状态的确定,我们用optij表示在i.j区间内可以获得的最大加分，用rootij表示i.j范围内选取哪个结点作为根时可以获得最大加分。 对区间i,j(ij)，我们定义optij=1; 则有： optij=max optik-1*optk+1j+valuek | k=i,i+1,i+2.j rootij为对应的k值,int search(int l, int r) if

30、(optlr != 0) return optlr; for (int i = l; i optlr) optlr = search(l, i - 1) * search(i + 1, r) + valuei; rootlr = i; memset(opt, 0, sizeof(opt); for (int i = 1; i = n + 1; i+) optii - 1 = 1; for (int i = 1; i = n; i+) optii = valuei; int Ans = search(1, n);,代码,上面几道题是区间动态规划的一些例题，它们的基础时间复杂度都是O(N3)的,聚

31、会的快乐(Party),你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的人。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人（姓名，他幽默的系数，以及他上司的名字），找到能使幽默系数和最大的若干个人。 输入 第一行一个整数N（N100）。接下来有N行，每一行描述一个人，信息之间用空格隔开。姓名是长度不超过20的字符串。幽默系数是在0到100之间的整数 输出 邀请的人最大的幽默系数和,分析,仔细看过这个问题之后，会发现这道题目和我们上面遇到的一些类型的动态规划都有点区别：它的数据并不是以线性或者表格的形式， 而是以树的形式进行存储的。 可以发现，这

32、道题目中的关系可以简单地描述为：在一棵树中，父亲结点和儿子结点不可以同时选取。而每个结点有一个权值，在满足上述条件的情况下求出可以选取出的最大值。 这就是我们所说的树形动态规划。由于树本身的递归性质，我们使用记忆化搜索的方法来完成子问题答案的存储。,状态的确定,显然，对于每个结点我们需要记录当前结点是否被取到，以及在该种情况下该子树所能获得的最大幽默系数。 因此，我们定义opt1i表示在编号为i的结点必取的情况下以i为根的子树所能获得的最大快乐值；相应地，opt0i表示在编号为i的结点不取的情况下以i为根的子树所能获得的最大幽默系数。 则根据题目中的要求，我们有 opt1i=valuei +

33、opt0k(k为所有i的子结点的编号) opt0i=maxopt0k,opt1k(k为所有i的子结点的编号) w数组用来存储边； ri存放编号为i的结点的儿子数； di中存放编号为i的结点的在w数组中最后一条边的编号，其中d0=0;di=di-1+ri;,int search(int flag, int lab) /记忆化搜索 if (optflaglab != 0) return optflaglab; int p = (flag = 1) ? valuelab : 0; for (int i = dlab - 1; i = dlab; i+) if (flag = 1) p += sear

34、ch(0, wi); else p += max(search(0, wi), search(1, wi); optflaglab = p; return p; memset(d, 0, sizeof(d); for (int i = 1; i = n; i+) di = di - 1 + ri; ans = max(search(1, root), search(0, root);,代码,二*苹果树,有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点） 这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述

35、一根树枝的位置。下面是一颗有4个树枝的树 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。,二*苹果树,输入格式 第1行2个数，N和Q(1=Q= N,1N=100)。N表示树的结点数，Q表示要保留的树枝数量。 接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000个。 输出格式 一个数，最多能留住的苹果的数量。,分析,同样，这道题目给出的数据是以树形结构连接的。 而且这道题很明确的告诉我们：每个结点只可能是叶节点或者拥有两个儿子。 因此，我们可以讨论每个结点伸出的两个树枝的剪枝情况，并且仍然用记忆化搜索完成。,状态的确定,我们用optij表示编号为i的结点作为根的子树中保留j个树枝可以获得的最大苹果数。 状态转移方程为： optij:=ma