《动态规划算法优秀课件.ppt》由会员分享，可在线阅读，更多相关《动态规划算法优秀课件.ppt（169页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划算法第1页，本讲稿共169页前言：各类信息学竞赛的重要考察内容。不同于其他算法和数据结构，没有固定的结构框架。对选手能力有较高要求（函数思想）。初学者不易掌握其思想，需要做大量的题。典型的问题。会做不代表真正掌握。主要是分析问题的方法和思路；其次是代码。2第2页，本讲稿共169页在三个竞赛中的首次出现：数字三角形【IOI 1994】石子合并【NOI 1995】导弹拦截【NOIP 1999】3第3页，本讲稿共169页目录：两个引例 动态规划的基本概念 动态规划的常见模型及例题4第4页，本讲稿共169页引例1：数字三角形【IOI 1994】有一个数字三角形，从最顶层出发，每一步只能向左下或
2、右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。下图数据的路应为:7-3-8-7-5，和为30。输入：第一行：n(1=n=100),数字三角形共有n行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且=100.输出：一个正整数，路径上数字之和的最大值。73 88 1 02 7 4 44 5 2 6 55第5页，本讲稿共169页6输入样例：573 88 1 02 7 4 44 5 2 6 5输出样例：30第6页，本讲稿共169页样例：i,ji+1,j i+1,j+17第7页，本讲稿共169页8第8页，本讲稿共169页路径数字最大和：7+3+8+7+5=3
3、09第9页，本讲稿共169页深度优先搜索算法：Procedure dfs(i,j,sum)/从(1,1)走到（i，j）位置所求和sumBegin if i=n then/走到最后一行 ans=max(ans,sum);exit;dfs(向左下方走)；dfs(向右下方走)；End;10第10页，本讲稿共169页代码实现：/二维数组ai,j存储数字三角形。procedure dfs(i,j,sum:integer);begin if i=n then begin if sumans then ans:=sum;exit;end;dfs(i+1,j,sum+ai+1,j);dfs(i+1,j+1,s
4、um+ai+1,j+1);end;初始：dfs(1,1,a1,1);结果：ansi,ji+1,j i+1,j+111i,ji+1,j i+1,j+1第1 1页，本讲稿共169页n=100 超时！12第12页，本讲稿共169页N=109263 5318 25 1463 85 9 3258 84 70 2 9388 25 35 0 20 119 96 85 6 14 97 6074 71 33 39 51 96 27 960 78 78 61 24 49 41 36 3032 23 16 32 31 32 56 76 74 8313第13页，本讲稿共169页每个位置被计算过的次数：1 1 1 1
5、2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 14第14页，本讲稿共169页代码实现：/二维数组ai,j存储数字三角形。procedure dfs(i,j,sum:integer);begin inc(counti,j);/全局计数器 if i=n then begin if sumans then ans:=sum;exit;end;dfs(i+1,j,sum+ai+1,j);dfs(i+1,
6、j+1,sum+ai+1,j+1);end;i,ji+1,j i+1,j+115第15页，本讲稿共169页搜索速度慢的原因是做了很多重复的计算实际上：从（i,j）走到最后一行；路线上和的最大值不变。9263 5318 25 1463 85 9 3258 84 70 2 9388 25 35 0 20 119 96 85 6 14 97 6074 71 33 39 51 96 27 960 78 78 61 24 49 41 36 3032 23 16 32 31 32 56 76 74 8316第16页，本讲稿共169页所以：第一次求完(i,j)到达最后一行的最大值后，用fi,j记录下来。以后
7、再遇到时不需要再搜索求解，可以直接使用fi,j，从而大大的节省时间。记忆化搜索17第17页，本讲稿共169页记忆化搜索算法：/ai,j记录数字三角形/fi,j:从(i,j)走到最后一行的和的最大值；初始-1Procedure dfs(i,j:integer);/求(i,j)到最后一行的最大和 begin if i=n then begin fi,j:=ai,j;exit;end;if fi,j=0 then exit;/已经求过了，无需再求 dfs(i+1,j);dfs(i+1,j+1);fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;end;dfs(1,1);ans=f1,1
8、;18i,ji+1,j i+1,j+1第18页，本讲稿共169页每个点的计算次数：n=101 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 N=100;问题解决了19第19页，本讲稿共169页思考记忆化搜索的求解过程：i,ji+1,ji+1,j+120fi,j:(i,j)到最后一行的和的最大值；Ans=f1,1第20页，本讲稿共169页换一种方法实现：/fi,j：从(i,j)走到最后一行的和的最大值；for i:=1 to n
9、 do fn,i:=an,i;/最后一行for i:=n-1 downto 1 do/从第n-1行向上求 for j:=1 to i do fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;writeln(f1,1);递推法：倒推21第21页，本讲稿共169页i,ji-1,j-1 i,j顺推：22fi,j：从(1,1)走到(i,j)的和的最大值；Ans=maxfn,i i:1.n第22页，本讲稿共169页顺推：/fi,j：从(1,1)走到(i,j)的和的最大值；f1,1:=a1,1;for i:=2 to n do for j:=1 to i do fi,j:=max(fi-1,
10、j-1,fi-1,j)+ai,j;ans:=fn,1;/找最大的fn,ifor i:=2 to n do if fn,ians then ans:=fn,i;writeln(ans);23边界情况?第23页，本讲稿共169页24边界问题的解决：方法一：var f:array0.100,0.100of longint;把第0行及第0列元素初始化为0。方法二：把fi,1和fi,i作为特殊情况单独处理，即：for i:=2 to n dobegin fi,1=fi-1,1+ai,1;fi,i=fi-1,i-1+ai,i;for j:=2 to i-1 do fi,j:=max(fi-1,j-1,fi
11、-1,j)+ai,j;end;第24页，本讲稿共169页回顾本题：重复的子问题。用表记录子问题的解，以后可以直接使用。有明显的阶段性。求解方法：记忆化搜索；递推。25第25页，本讲稿共169页引例2：公共汽车【问题描述】一个城市的道路，南北向的路有n条，并由西向东从1标记到n,东西向的路有m条，并从南向北从1标记到m,每一个交叉点代表一个路口，有的路口有正在等车的乘客。一辆公共汽车将从(1,1)点驶到（n,m）点，车只能向东或者向北开.问：司机怎么走能接到最多的乘客。nm(n,m)26北南西 东第26页，本讲稿共169页【输入】第一行是n,m和k,其中k是有乘客的路口的个数。以下k行是有乘客的
12、路口的坐标和乘客的数量。已知每个路口的乘客数量不超过1000000。n,m=1000.【输出】接到的最多的乘客数。bus.in bus.out8 7 114 3 46 2 42 3 25 6 12 5 21 5 52 1 13 1 17 7 17 4 28 6 21127第27页，本讲稿共169页 ai,j:(i,j)位置的人数;fi,j:从(1,1)走到(i,j)能接的最多人数。fi,j:=maxfi-1,j,fi,j-1+ai,j28第28页，本讲稿共169页递推实现：var f0.1000,0.1000of longint;fillchar(f,sizeof(f),0);for i:=1
13、 to n do/按列 for j:=1 to m do/按行 fi,j:=max(fi-1,j,fi,j-1)+ai,j;writeln(fn,m);29第29页，本讲稿共169页二、动态规划的基本概念 动态规划（Dynamic Programming 简称DP）。解决“多阶段决策问题”的一种高效算法。通过合理组合子问题的解从而解决整个问题解的一种算法。其中的子问题并不是独立的，这些子问题又包含有公共的子子问题。动态规划算法就是对每个子问题只求一次，并将其结果保存在一张表中(数组)，以后再用到时直接从表中拿过来使用，避免重复计算相同的子问题。“不做无用功”的求解模式，大大提高了程序的效率。动
14、态规划算法常用于解决统计类问题（统计方案总数）和最优值问题（最大值或最小值），尤其普遍用于最优化问题。30第30页，本讲稿共169页定义：fi,j：从(i,j)走到最后一行的和的最大值；目标：f1,1倒推求解过程fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;31第31页，本讲稿共169页 1、阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。阶段的划分一般根据时间和空间来划分的。2、状态：某一阶段的出发位置成为状态，通常一个阶段有多个状态。状态通常
15、可以用一个或一组数来描述，称为状态变量。3、决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。描述决策的变量称决策变量 4、策略和最优策略 所有阶段的决策有序组合构成一个策略。最优效果的策略叫最优策略。32动态规划的术语：第32页，本讲稿共169页33例：最短路径问题 现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？AB1B2C1C2C3C4D1D2D3E5316384 38556343第33页，本讲稿共169页34阶段1 阶段2 阶段3 阶段4 阶段5第1部分：A第2部分：B1，B2第3部分：C1，C2，C3，C4第4部分：
16、D1，D2，D3第5部分：EAB1B2C1C2C3C4D1D2D3E5316384 38556343第34页，本讲稿共169页35定义f(i)为i点到E的最短距离，d(i,j)为节点i到节点j的距离。倒推的方法来求A到E的最短距离。第5阶段:f(E)=0;第4阶段:f(D1)=3;f(D2)=4;f(D3)=3第3阶段:f(C1)=mind(C1,D1)+f(D1),d(C1,D2)+f(D2)=min8,10=8 f(C2)=d(C2,D1)+f(D1)=8 f(C3)=d(C3,D3)+f(D3)=11 f(C4)=d(C4,D3)+f(D3)=6第2阶段:f(B1)=mind(B1,C1
17、)+f(C1),d(B1,C2)+f(C2),d(B1,C3)+f(C3)=min1+8,6+8,3+11=9 f(B2)=mind(B2,C2)+f(c2),d(B2,C4)+f(C4)=min8+8,4+6=10第1阶段:f(A)=mind(A,B1)+f(B1),d(A,B2)+f(B2)=min5+9,3+10=13最短路径：A-B2-C4-D3-E最短距离：13第35页，本讲稿共169页36fkx=minfk+1yi+d x,yi状态转移方程：由已求得的状态来求未知状态的递推关系式称为状态转移方程。Xy1y2yiEFx:x到终点的最短距离。目标是f1A倒推：第36页，本讲稿共169页
18、37fkx=minfk-1yi+d yi,xFx:起点到x最短距离。目标是f5E顺推：Xy1y2yiA第37页，本讲稿共169页38一般形式：U：状态；X：策略顺推：fUk=optfUk-1+LUk-1,Xk-1 LUk-1,Xk-1：状态Uk-1通过策略Xk-1到达状态Uk 的费用 初始fU1；结果：f(Un)第38页，本讲稿共169页39一般形式：U：状态；X：策略倒推：fUk=optfUk+1+LUk,XkLUk,Xk：状态Uk通过策略Xk到达状态Uk+1 的费用初始fUn；结果：f(U1)第39页，本讲稿共169页40动态规划问题的特征:1、最优子结构 如果问题的一个最优解中包含了子问
19、题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。2、重叠子问题 在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。第40页，本讲稿共169页3、无后效性原则41已经求得的状态，不受未求状态的影响。第41页，本讲稿共169页42最优子结构、重叠子问
20、题、无后效性阶段1 阶段2 阶段3 阶段4 阶段5AB1B2C1C2C3C4D1D2D3E5316384 38556343第42页，本讲稿共169页43第43页，本讲稿共169页44 拓扑图（有向无环图）无后效性第44页，本讲稿共169页45 非拓扑图（可能有环）有后效性 a b c？b c a？abc51111第45页，本讲稿共169页46动态规划的条件：无后效性、最优子问题 无后效性、最优子问题是否能满足与 状态的表示、阶段的划分、状态的转移有关第46页，本讲稿共169页47 1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值
21、；记忆化搜索（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。设计动态规划法的步骤：第47页，本讲稿共169页48 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）.定量处理的过程也就是决策实施的过程.动态规划的关键：第48页，本讲稿共169页49fUn=初始值；for kn-1 downto 1 do/枚举阶段 for U取遍所有状态 do/枚举状态 for X取遍所有决策 do/枚举决策 fUk=optfUk+1+LUk,Xk；LUk,Xk：状态Uk通过策略Xk到
22、达状态Uk+1的费用输出：fU1:目标动态规划的一般倒推格式为：第49页，本讲稿共169页50/fi,j：从(i,j)走到最后一行的和的最大值；for i:=1 to n do fn,i:=an,i;/初始for i:=n-1 downto 1 do/阶段 for j:=1 to i do/状态 fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;/决策writeln(f1,1);第50页，本讲稿共169页51fU1=初始值；for k2 to n do/枚举每一个阶段 for U取遍所有状态 do for X取遍所有决策 do fUk=optfUk-1+LUk-1,Xk-1；LU
23、k-1,Xk-1：状态Uk-1通过策略Xk-1到达状态Uk 的费用输出：fUn:目标动态规划的一般顺推格式为：第51页，本讲稿共169页顺推：/fi,j：从(1,1)走到(i,j)的和的最大值；f1,1:=a1,1;/初始化for i:=2 to n do/阶段 for j:=1 to i do/状态 fi,j:=max(fi-1,j-1,fi-1,j)+ai,j;/决策/找最大的fn,ians:=fn,1;for i:=2 to n do if fn,ians then ans:=fn,i;writeln(ans);52第52页，本讲稿共169页53贪心算法：采用“自顶向下”的方式使用最优子
24、结构：先做决策，选在当时看起来是最优的选择（只顾眼前利益），然后再求解决策后的那个子问题。“先决策，再求解子问题”DP:“先求得子问题的解，然后决策”。7 3 8 8 1 0 2 7 4 44 5 2 6 5动态规划与贪心算法的不同：第53页，本讲稿共169页通过做大量的题目，慢慢理解和体会DP 其中的54第54页，本讲稿共169页三、DP 常见模型55线性型坐标型区间型背包型树型动态规划有多种多样的题目，通常按照状态可分为以下几类：第55页，本讲稿共169页（一）、线性模型56 线性动态规划状态是一维的（fi）。正推：第i个元素的最优值只与前i-1个元素的最优值有关。倒推：第i个元素的最优值
25、只第i+1个元素之后的最优值有关。经典的线性DP题目有最长上升子序列、最大连续子序列和、最长公共子序列等。第56页，本讲稿共169页1.最长上升子序列模型57 例1 导弹拦截【NOIP 1999】【问题描述】某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统，但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，不能拦截所有的导弹，输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），请聪明的你帮忙计算这套系统最多能拦截多少导弹。【输入】第一行：n（=1000
26、），敌国导弹的数量。第二行：n个整数，用空格分隔，依次是敌国导弹的高度(30000)。【输出】最多拦截敌国导弹的数量。【数据规模】对于100%的数据：n=1000。第57页，本讲稿共169页58【样例输入输出】bumb.in bumb.out82 7 1 9 10 1 2 34题意简述：给定n个元素的数列，求最长的上升子序列长度。即：在原序列中，最多能选多少个数，在原有顺序下递增。第58页，本讲稿共169页最长上升子序列长度（LIS）：59 最长上升子序列显然是以某一个ai作为第一元素的一个最长上升子序列。如果求出以原序列中每一个元素ai作为第一个元素开头的最长上升子序列长度fi.那么:ans
27、=maxfi；i=1.n 问题是怎么求fi?8 2 7 1 9 10 1 4 3第59页，本讲稿共169页倒推法：60ai:数列中的第i个数。fi:以ai为开始(ai是被选中的第一个元素)的最长递增子序列的序列长度。转移方程：fi=maxfj+1 条件：ij=n并且aiaj边界：fn=1;目标：maxfi;1=i=n8 2 7 1 9 10 1 4 3第60页，本讲稿共169页倒推参考程序：61fn:=1;for i:=n-1 downto 1 do begin for j:=i+1 to n do if(ajai)and(fjfi)then fi:=fj;/找最大的fj inc(fi);/包
28、含ai end;ans:=f1;for i:=2 to n do if fians then ans:=fi;writeln(ans);第61页，本讲稿共169页顺推：62ai:数列中的第i个数。fi:以ai为结尾(ai是被选中的最后一个元素)的最长递增子序列的序列长度。fi=maxfj+1 条件：1=ji并且ajai边界：f1=1;目标：maxfi;1=i=n8 2 7 1 9 10 1 4 3第62页，本讲稿共169页顺推参考程序：63f1:=1;for i:=2 to n do begin for j:=1 to i-1 do if(ajfi)then fi:=fj;/找最大的fj inc(fi);/包含ai end;ans:=f1;for i:=2 to n do if fians then ans:=fi;writeln(ans);第63页，本讲稿共169页最长上升子序列长度（LIS）：64 倒推：fi:以ai为开始元素的最长递增子序列的序列长度。转移方程：fi=maxfj+1 条件：ij=n并且aiaj边界：fn=1;目标：maxfi;1=i=n第64页，本讲稿共169页顺推：65 fi:以ai为结尾的最长递增子序列的序列长度。fi=maxfj+1 条件：1=ji并且ajai边界：f1=1;目标：maxfi;1=i=n时间复杂度：O(n2)第65页，本讲稿共169页