动态规划的分类解析ppt课件.ppt

《动态规划的分类解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《动态规划的分类解析ppt课件.ppt（81页珍藏版）》请在三一办公上搜索。

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

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

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

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

5、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=minopti-1j,optij-1)+aij;最后输出optnn;,代码,for(int i=1;i=n;i+)for(int j=1;j=n;j

7、+)scanf(“%d”,乘积最大,国际数学联盟确定的“2000世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛活动，你的好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N(N40)的数字串，要求选手使用M(M6)个乘号将它分成M+1个部分，找出一种分法，使得这M+1个部分的乘积最大。同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：有一个数字串：312，当N=3，M=1时会有两种分法：312=36312=62这时，符合题目要求的结果是：312=62。现在，请你帮助你的好朋

8、友XZ设计一个程序，求得正确的答案。,分析,由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。显然，运算任何整数类型都无法容纳如此之大的数据，只能采用高精度运算，限于篇幅，对于高精度的加法运算、乘法运算和比较大小的运算，这里不作介绍，只是对的乘号最佳插入方式进行探讨：假设s1si(2in)中插入j个乘号，其中s1sk中插入了j-1个乘号，即乘式中的第j+1项为sk+1si(jki-1)：,分析,设ansij长度为i的数串中插入j个乘号的最大乘积（整型数组）。显然ansi0=s1.si对应的整型数组；ansij=maxanskj-1sk+1.si（1in，1jmin

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

10、r 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输出最大乘积ansnm；,过河,在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（

11、其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。,分析,从正面来考虑的话，这个问题是一个搜索性的问题，需要考虑从当前点出发可以跳到的所有点。然而从反面考虑的话，我们只需要考虑那些能到用一步到达当前点的所有点中，踩到石头数最小的那个。即opti=minoptk(max0,i-tki-s)+brii;,代码,

12、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)，同时有n件物品(0n30)，每件物品有一个体积vi(正整数)。要求从这n件物品中任取若干件装入箱内，使箱子的剩余空间最小。,分析,这是一个最基础的背包问题，只需要考虑选取哪几个物品放入箱子，可以使得剩余体积最小。这道题的基本做法当然还是穷举放进背包的

13、物品编号。若我们把取该物品记为1，不取该物品记为0，那么使用某种放入方式将对应一个2进制串，因此这类问题也被称为0-1背包问题.如果我们不从物品角度考虑，而是从体积角度考虑的话，就会发现，这个问题还可以被描述为，wi的体积是否能由这些物品得到。,状态的确定,我们用optij（布尔）表示前i个物品是否能达到j体积。则optij的值取决于前i-1个物品能否达到j体积，或者是前i-1个物品能否达到j-vi体积则有optij=(opti-1j-vi)or(opti-1j)初值为opt00=true；其他都为false,代码,memset(opt,0,sizeof(opt);opt00=1;for(in

14、t i=1;i=vi)optij=opti-1j|opti-1j-vi;else optij=opti-1j;,采药,辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”输入的第一行有两个整数T(1T1000)和N(1N100)，用一个空格隔开，T代表总共能够用来采药的时间，

15、N代表山洞里的草药的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。,分析,和上面一个问题一样，这个问题同样可以采用搜索解决，然而搜索的时间复杂度也同样相当的可怕。那我们可不可以借鉴一下上面的想法来解决这个问题呢？,状态的确定,答案是肯定的。类似地，我们用optij表示前i个物体在j时间内的一个参数。但是我们在里面存的值并不是能否达到，而是在这个状态下可以达到的最大价值。但是状态的转移方程稍微有些差别，除了考虑opti-1j-ti和opti-1j之外，还要考虑optij-1(这样可以最后直接输出optnmaxt从而省掉一次扫描

16、)，即optij表示前i个物体在j时间内可以达到的最大价值，注意这里包括不足j时间的情况。,代码,memset(opt,0,sizeof(opt);opt00=0;for(int i=1;i=vi)optij=maxopti-1j,opti-1j-ti+valuei,optij-1 else optij=maxopti-1j,optij-1;printf(%dn,optnmaxt);,Dairy Queen,奶牛Bassie去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬

17、币面值为ai。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1=total=1000,1=n=1000,1=ai=300)求一共有多少种解决方案？【输入】第一行为硬币总值total和硬币种类数n。以下n行为数值ai，i=1,2,3.n【输出】一行，解决方案数,分析,这道题目和上面的采药的区别仅仅在于，每个物品可以无限次的取。当然，这样的问题仍然可以用背包模型来解决，我们将这种模型称为无限背包。在这种情况下，我们只要把opti-1j-ai改成optij-ai,即允许一种物品被取多次。由于是计数，所以optij=optij-ai+opti-1j。一个重要的优化：我

18、们可以把opt数组压缩成长度为total的一维数组，因为这样是不会影响结果的，但可以大大降低它的空间复杂度。,状态的确定,我们用optj表示硬币总面值为j时共有多少种方法optj=optj+optj-ai(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。求解将哪些物品装入背包可使这些

19、物品的体积总和不超过背包容量，且价值总和最大。输入样例100 3 maxv,n70 40 20 v1,v2,vn50 40 30 w1,w2,wn1 2 3 m1,m2,m3,mn,分析,本题和无限背包问题很类似。基本的方程只需将无限背包问题的方程略微一改即可，因为对于第i种物品有mi+1种策略：取0件，取1件取 mi件。令fiv表示前i种物品恰放入一个容量为v的背包的最大价值，则：fiv=maxfi-1v-kvi+kwi|0=k=mi。时间复杂度是O(Vmi)。另一种好想好写的基本方法是转化为0-1有限背包求解：把第i种物品换成mi件该物品，即转化成了物品数为mi的0-1有限背包问题，直接求

20、解，复杂度仍然是O(Vmi)。但是我们期望将它转化为有限背包问题之后能够降低时间复杂度。,分析,应用二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略取0.mi件均能等价于取若干件代换以后的物品。另外，取超过mi件的策略必不能出现。方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的体积和价值均是原来的体积和价值乘以这个系数。使这些系数分别为 1,2,4,.,2(k-1),mi-2k+1，且k是满足mi-2k+10的最大整数。例如，如果mi为13，就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为mi，表明不可能

21、取多于mi件。另外这种方法也能保证对于0.mi间的每一个整数，均可以用若干个系数的和表示。这样就将第i种物品分成了(log mi)种物品，将原问题转化为了复杂度为O(Vlog mi)的有限背包问题，是很大的改进。,k=0;/转化后物品的个数for(int i=1;i 0)if(mi=t)k+;v1k=vi*t;w1k=wi*t;mi=mi-t;t=1;else k+;v1k=vi*mi;w1k=wi*mi;mi=0;,代码,for(int i=1;i=vi;j-)if(optj-v1i+w1i optj)optj=optj-v1i+w1i;if(optj best)best=optj;prin

22、tf(%dn,best);,代码,以上都是背包问题的一些例题，他们的基础时间复杂度都是O(mn)的,最小代价子母树,问题描述：有n堆沙子排成一排，每堆沙子有一个数量，例如：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个数给出

23、后，找出一种合理的归并方法，使得总代价最小。,分析,（1）如果把归并14堆看成整个问题，则这个问题可以分解为三个归并方案，每个归并方案包含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）归并树所有叶结点的权值之和而对于op

24、t数组中的子区间数值的取值大小，我们有两种渠道来获取：（1）利用普通的dp，枚举开始结点和区间长度来进行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,多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在

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

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

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

28、+(value1i+valuej+1.n)*(posj-posi);rightij=minleftij-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的右子树的加

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

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

31、)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)的,聚会的快乐(Party),你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的人。但是劝你不要同时邀请某个人和

32、他的上司，因为这可能带来争吵。给定N个人（姓名，他幽默的系数，以及他上司的名字），找到能使幽默系数和最大的若干个人。输入第一行一个整数N（N100）。接下来有N行，每一行描述一个人，信息之间用空格隔开。姓名是长度不超过20的字符串。幽默系数是在0到100之间的整数输出邀请的人最大的幽默系数和,分析,仔细看过这个问题之后，会发现这道题目和我们上面遇到的一些类型的动态规划都有点区别：它的数据并不是以线性或者表格的形式，而是以树的形式进行存储的。可以发现，这道题目中的关系可以简单地描述为：在一棵树中，父亲结点和儿子结点不可以同时选取。而每个结点有一个权值，在满足上述条件的情况下求出可以选取出的最大值

33、。这就是我们所说的树形动态规划。由于树本身的递归性质，我们使用记忆化搜索的方法来完成子问题答案的存储。,状态的确定,显然，对于每个结点我们需要记录当前结点是否被取到，以及在该种情况下该子树所能获得的最大幽默系数。因此，我们定义opt1i表示在编号为i的结点必取的情况下以i为根的子树所能获得的最大快乐值；相应地，opt0i表示在编号为i的结点不取的情况下以i为根的子树所能获得的最大幽默系数。则根据题目中的要求，我们有opt1i=valuei+opt0k(k为所有i的子结点的编号)opt0i=maxopt0k,opt1k(k为所有i的子结点的编号)w数组用来存储边；ri存放编号为i的结点的儿子数；

34、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+=search(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

35、-1+ri;ans=max(search(1,root),search(0,root);,代码,二*苹果树,有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。,二*苹果树,输入格式第1行2个数，N和Q(1=Q=N,1N=100)。N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数，

36、前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。输出格式一个数，最多能留住的苹果的数量。,分析,同样，这道题目给出的数据是以树形结构连接的。而且这道题很明确的告诉我们：每个结点只可能是叶节点或者拥有两个儿子。因此，我们可以讨论每个结点伸出的两个树枝的剪枝情况，并且仍然用记忆化搜索完成。,状态的确定,我们用optij表示编号为i的结点作为根的子树中保留j个树枝可以获得的最大苹果数。状态转移方程为：optij:=maxopti.rcj-1+valuei.rc,(剪掉左枝)opti.lcj-1+valuei.lc,(剪掉右枝)maxopti.lck+o

37、pti.rcj-2-k+valuei.lc+valuei.rc(0=k=j-2)(左枝和右枝都不剪),int search(int lab,int num)if(optlabnum!=0)return optlabnum;if(lclab=0|num=0)return 0;int l=lclab,r=rclab;if(search(r,num-1)+valueroptlabnum)optlabnum=optrnum-1+valuer;if(search(l,num-1)+valueloptlabnum)optlabnum=optlnum-1+valuei;for(int i=0;i optla

38、bnum)optlabnum=optli+optrnum-2-i+valuel+valuer;return optlabnum;,代码,选课,问题描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课只有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？,选课,输入：第一行有两个整数N,M用空格隔。(1=N=200,1=M=150)接下来的N行,第i+1行包含

39、两个整数ki和si，ki表示第i门课的直接先修课，si表示第i门课的学分。若ki=0表示没有直接先修课（1=ki=N,1=si=20）。输出：只有一行，选M门课程的最大得分。,分析,同样，这道题目给出的数据是以树形结构连接的。这题比苹果树多了一个步骤就是把一棵多叉树转化为二叉树。读入数据时把二叉树建好：把一门课的先修课作为它的父亲。一个结点的第一个孩子作为父节点的左子树，其它孩子作为第一个孩子的右子树。,状态的确定,Fxy：表示节点x取y门课得最高学分，则Fxy=maxfx.ry,fx.lk-1+x.v+f(x.r,y-k)|k=1,2,.yfx.ry：表示不选课程x，右孩子选k门课。fx.l

40、k-1+x.v(课程x的学分)：表示选了课程x,左孩子选k-1门课,共k门课。f(x.r,y-k)表示右孩子只能选y-k门课。标程中节点-1表示空节点，0是根节点，1-n是n门可选课程的节点。,void treedp(int x,int y)if(fxy 0)return;treedp(ax.r,y);/只有右子树的情况fxy=fax.ry;for(int k=1;k=y;k+)/左右子树都有的情况treedp(ax.l,k-1);treedp(ax.r,y-k);if(fxy fax.lk-1+fax.ry-k+ax.v)fxy=fax.lk-1+fax.ry-k+ax.v,代码,这些题是树

41、形动态规划的典型例题，类似的题目还有很多，在这就不一一列举了,看完了这么多题目之后，我们再来总结一下动态规划的重点和难点,上面所有的问题都可以用穷举和搜索来解决，但是比较之下动态规划却有很明显的时间优势，采取的是牺牲空间换取时间的方法。在整个思考过程中，我们通常是采取换一个角度来考虑问题的方法，巧妙地把其中的某个参数转化成维度，从而将原本需要大量重复计算的东西存下来，随时方便调用。因此，想要用好动态规划，必须得学会转化思考角度，充分利用空间来节省时间。,同时，我们也必须看到，在DP问题的思考过程中，最关键的两个东西就是状态的确定和转移方程。这也是在运用动态规划的过程中的难点之一。,当然，动态规划也不是万能的。比如之前提到的数塔问题中，如果是要求一条路径使得最终结果最接近0的话，那么DP也无能为力了。只有在满足前面所提到的最优子结构性质和不具有后效性的两个前提下，动态规划才能发挥它的作用。,The End Thanks,