动态规划算法优秀PPT.ppt

《动态规划算法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《动态规划算法优秀PPT.ppt（169页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划算法第1页，本讲稿共169页前言：前言：各类信息学竞赛的重要考察内容。各类信息学竞赛的重要考察内容。不同于其他算法和数据结构，没有固定的结构不同于其他算法和数据结构，没有固定的结构框架。框架。对选手能力有较高要求（函数思想）。对选手能力有较高要求（函数思想）。初学者不易掌握其思想，需要做大量的题。初学者不易掌握其思想，需要做大量的题。典型的问题。典型的问题。会做不代表真正掌握。会做不代表真正掌握。主要是分析问题的方法和思路；其次是代码。主要是分析问题的方法和思路；其次是代码。2第2页，本讲稿共169页在三个竞赛中的首次出现：在三个竞赛中的首次出现：数字三角形数字三角形【IOI 1994

2、】石子合并石子合并 【NOI 1995】导弹拦截导弹拦截 【NOIP 1999】3第3页，本讲稿共169页目录：目录：两个引例动态规划的基本概念动态规划的常见模型及例题4第4页，本讲稿共169页引例引例1 1：数字三角形【：数字三角形【IOI 1994IOI 1994】有一个数字三角形，从最顶层出发，每一步只能向左下或右下有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。下图数据的路应为和的最大值。下图数据的路应为:7-3-8-7-57-3-8-7-5，和为，和为

3、3030。输入：输入：第一行：第一行：n(1=n=100),n(1=n=100),数字三角形共有数字三角形共有n n行；行；以下以下R R行：依次表示数字三角形中每行中的数字。行：依次表示数字三角形中每行中的数字。每个数都是非负的，且每个数都是非负的，且=100.ans then ans:=sum;if sumans then ans:=sum;exit;exit;end;end;dfs(i+1,j,sum+ai+1,j);dfs(i+1,j,sum+ai+1,j);dfs(i+1,j+1,sum+ai+1,j+1);dfs(i+1,j+1,sum+ai+1,j+1);end;end;初始：初

4、始：dfs(1,1,a1,1);结果：结果：ansi,ji+1,ji+1,j+111i,ji+1,ji+1,j+1第11页，本讲稿共169页n=100 nans then ans:=sum;if sumans then ans:=sum;exit;exit;end;end;dfs(i+1,j,sum+ai+1,j);dfs(i+1,j,sum+ai+1,j);dfs(i+1,j+1,sum+ai+1,j+1);dfs(i+1,j+1,sum+ai+1,j+1);end;end;i,ji+1,ji+1,j+115第15页，本讲稿共169页搜索速度慢的原因是做了很多搜索速度慢的原因是做了很多重复重

5、复的计算的计算实际上：实际上：从（从（i,j）走到最后一行；路线上和的最大值不变。）走到最后一行；路线上和的最大值不变。9263 5318 25 1463 85 9 3258 84 70 2 9388 2525 3535 0 20 119 96 8585 6 14 97 6074 71 3333 39 51 96 27 960 78 7878 61 24 49 41 36 3032 23 16 3232 31 32 56 76 74 8316第16页，本讲稿共169页所以：所以：第一次求完第一次求完(i,j)到达最后一行的最大值后，用到达最后一行的最大值后，用fi,j记录下来。记录下来。以后再

6、遇到时不需要再搜索求解，可以直接使用以后再遇到时不需要再搜索求解，可以直接使用fi,j，从，从而大大的节省时间。而大大的节省时间。记忆化搜索17第17页，本讲稿共169页记忆化搜索算法：记忆化搜索算法：/ai,j/ai,j记录数字三角形记录数字三角形/fi,jfi,j:从从(i,j)(i,j)走到最后一行的和的走到最后一行的和的最大值最大值；初始；初始-1-1Procedure dfs(i,j:integer);Procedure dfs(i,j:integer);/求求(i,j)(i,j)到最后一行的最大和到最后一行的最大和 beginbegin if i=n then if i=n the

7、n begin begin fi,j:=ai,jfi,j:=ai,j;exit;exit;end;end;if fi,j=0 then exitif fi,j=0 then exit;/已经求过了，无需再求已经求过了，无需再求 dfs(i+1,j);dfs(i+1,j);dfs(i+1,j+1);dfs(i+1,j+1);fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;end;end;dfs(1,1);dfs(1,1);ans=f1,1;ans=f1,1;18i,ji+1,ji+1,j+1第18页，本讲稿共169页

8、每个点的计算次数：每个点的计算次数：n=10n=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;Nans then ans:=fn,i;if fn,ians then ans:=fn,i;writeln(ans);writeln(ans);23边界情况?第23页，本讲稿共169页24边界问题的解决：边界问题的解决：方法一：方法一：var f:array0.100,0.100of longint;var f:a

9、rray0.100,0.100of longint;把第把第0 0行及第行及第0 0列元素初始化为列元素初始化为0 0。方法二：方法二：把把fi,1fi,1和和fi,ifi,i作为特殊情况单独处理，即：作为特殊情况单独处理，即：for i:=2 to n dofor i:=2 to n dobeginbegin fi,1=fi-1,1+ai,1;fi,1=fi-1,1+ai,1;fi,i=fi-1,i-1+ai,i;fi,i=fi-1,i-1+ai,i;for j:=2 to i-1 do for j:=2 to i-1 do fi,j:=max(fi-1,j-1,fi-1,j)+ai,j;f

10、i,j:=max(fi-1,j-1,fi-1,j)+ai,j;end;end;第24页，本讲稿共169页回顾本题：回顾本题：重复的子问题。重复的子问题。用表记录子问题的解，以后可以直接使用。用表记录子问题的解，以后可以直接使用。有明显的阶段性。有明显的阶段性。求解方法：记忆化搜索；递推。求解方法：记忆化搜索；递推。25第25页，本讲稿共169页引例引例2 2：公共汽车：公共汽车【问题描述】【问题描述】一个城市的道路，南北向的路有一个城市的道路，南北向的路有n条，并由西向东从条，并由西向东从1标记到标记到n,东西向的东西向的路有路有m条，并从南向北从条，并从南向北从1标记到标记到m,每一个交叉点

11、代表一个路口，有的路每一个交叉点代表一个路口，有的路口有正在等车的乘客。一辆公共汽车将从口有正在等车的乘客。一辆公共汽车将从(1,1)点驶到（点驶到（n,m）点，车只）点，车只能向东或者向北开能向东或者向北开.问：司机怎么走能接到最多的乘客。问：司机怎么走能接到最多的乘客。nm(n,m)26北北南南西西东东第26页，本讲稿共169页【输入】【输入】第一行是第一行是n,m和和k,其中其中k是有乘客的路口的个数。是有乘客的路口的个数。以下以下k行是有乘客的路口的坐标和乘客的数量。已知每个路口的行是有乘客的路口的坐标和乘客的数量。已知每个路口的乘客数量不超过乘客数量不超过1000000。n,mB2-

12、C4-D3-E最短距离：最短距离：13第35页，本讲稿共169页36fkx=minfk+1yi+d x,yi状态转移方程：状态转移方程：由已求得的状态来求未知状态的递推关系式称为状态转移方程。Xy1y2yiEFx:xFx:x到终点的最短距离。目标是到终点的最短距离。目标是f f1 1AA倒推：倒推：第36页，本讲稿共169页37fkx=minfk-1yi+d yi,xFx:Fx:起点到起点到x x最短距离。目标是最短距离。目标是f f5 5EE顺推：顺推：Xy1y2yiA第37页，本讲稿共169页38一般形式：一般形式：U：状态；X：策略：策略顺推：顺推：fUk=optfUk-1+LUk-1,

13、Xk-1 LUk-1,Xk-1：状态状态Uk-1通过策略通过策略Xk-1到达状态到达状态Uk 的费用的费用 初始初始fU1；结果：；结果：f(Un)第38页，本讲稿共169页39一般形式：一般形式：U：状态；X：策略：策略倒推：倒推：fUfUk k=optfU=optfUk+1k+1+LU+LUk k,X,Xk k LULUk k,X,Xk k：状态状态U Uk k通过策略通过策略X Xk k到达状态到达状态U Uk+1k+1 的费用的费用初始初始fUfUn n；结果：；结果：f(Uf(U1 1)第39页，本讲稿共169页40动态规划问题的特征动态规划问题的特征 :1 1、最优子结构、最优子结

14、构 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。2 2、重叠子问题、重叠子问题 在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。第40页，本讲稿共169页3、无后效性原则41已经求得的状态，不受未求状态的影响

15、。已经求得的状态，不受未求状态的影响。第41页，本讲稿共169页42最优子结构、重叠子问题、无后效性最优子结构、重叠子问题、无后效性阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E531638438556343第42页，本讲稿共169页43第43页，本讲稿共169页44拓扑图（有向无环图）无后效性第44页，本讲稿共169页45非拓扑图（可能有环）有后效性 abc？bca？abc51111第45页，本讲稿共169页46动态规划的条件：动态规划的条件：无后效性、最优子问题无后效性、最优子问题无后效性、最优子问题是否能满足与 状态的表示、阶段的划分、状态的转

16、移有关第46页，本讲稿共169页47 1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；记忆化搜索（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。设计动态规划法的步骤：第47页，本讲稿共169页48 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）.定量处理的过程也就是决策实施的过程.动态规划的关键：第48页，本讲稿共169页49fUfUn n=初始值；初始值；for kfor kn-1 downto

17、 1 do /n-1 downto 1 do /枚举阶段枚举阶段 for Ufor U取遍所有状态取遍所有状态 do /do /枚举状态枚举状态 for X for X取遍所有决策取遍所有决策 do /do /枚举决策枚举决策 fU fUk k=optfU=optfUk+1k+1+LU+LUk k,X,Xk k；LULUk k,X,Xk k：状态状态U Uk k通过策略通过策略X Xk k到达状态到达状态U Uk+1k+1的费用的费用输出：输出：fUfU1 1:目标目标动态规划的一般动态规划的一般倒推倒推格式为：格式为：第49页，本讲稿共169页50/fi,j/fi,j ：从：从(i,j)(i

18、,j)走到最后一行的和的最大值；走到最后一行的和的最大值；for i:=1 to n do fn,i:=an,i;for i:=1 to n do fn,i:=an,i;/初始初始for i:=n-1 downto 1 do for i:=n-1 downto 1 do /阶段阶段 for j:=1 to i do for j:=1 to i do /状态状态 fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;/决策决策writeln(f1,1);writeln(f1,1);第50页，本讲稿共169页51fUfU1

19、1=初始值；初始值；for kfor k2 to n do 2 to n do /枚举每一个阶段枚举每一个阶段 for Ufor U取遍所有状态取遍所有状态 dodo for X for X取遍所有决策取遍所有决策 dodo fU fUk k=optfU=optfUk-1k-1+LU+LUk-1k-1,X,Xk-1k-1；LULUk-1k-1,X,Xk-1k-1：状态状态U Uk-1k-1通过策略通过策略X Xk-1k-1到达状态到达状态U Uk k 的费用的费用输出：输出：fUfUn n:目标目标动态规划的一般动态规划的一般顺推顺推格式为：格式为：第51页，本讲稿共169页顺推：顺推：/fi

20、,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贪心算法：采用“自顶向下”的方式使用最优子结构：先做决策，选在当时看起来是最优的选择（只顾眼前利益），然后再求解决策后的那个子问题。“先决策，

21、再求解子问题”DP:“先求得子问题的解，然后决策”。7 3 8 8 1 0 2 7 4 44 5 2 6 5动态规划与贪心算法的不同：第53页，本讲稿共169页通过做大量的题目，慢慢理解和通过做大量的题目，慢慢理解和体会体会DPDP其中的其中的54第54页，本讲稿共169页三、三、DPDP常见模型常见模型55线性型线性型坐标型坐标型区间型区间型背包型背包型树型树型动态规划有多种多样的题目，通常按照状态可分动态规划有多种多样的题目，通常按照状态可分为以下几类：为以下几类：第55页，本讲稿共169页（一）、线性模型（一）、线性模型56线性动态规划状态是一维的（线性动态规划状态是一维的（fi）。）。

22、正推：第正推：第i个元素的最优值只与前个元素的最优值只与前i-1个元素的最优值个元素的最优值有关。有关。倒推：第倒推：第i个元素的最优值只第个元素的最优值只第i+1个元素之后的最个元素之后的最优值有关。优值有关。经典的线性经典的线性DP题目有最长上升子序列、最大连续题目有最长上升子序列、最大连续子序列和、最长公共子序列等。子序列和、最长公共子序列等。第56页，本讲稿共169页1.1.最长上升子序列模型最长上升子序列模型57例例1 导弹拦截导弹拦截【NOIP 1999】【问题描述】【问题描述】某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统，但是这种导弹某国为了防御敌国的导弹袭击，研发出一种导

23、弹拦截系统，但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，后每一发炮弹都要高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，不能拦截所有的导弹，输入敌国导弹依次飞来由于该系统还在试用阶段，不能拦截所有的导弹，输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于的高度（雷达给出的高度数据是不大于30000 的正整数），请聪明的你帮忙计的正整数），请聪明的你帮忙计算这套系统最多能拦截多少导弹。算这套系统最多能拦截多

24、少导弹。【输入】【输入】第一行：第一行：n（=1000），敌国导弹的数量。），敌国导弹的数量。第二行：第二行：n个整数，用空格分隔，依次是敌国导弹的高度个整数，用空格分隔，依次是敌国导弹的高度(30000)。【输出】【输出】最多拦截敌国导弹的数量。最多拦截敌国导弹的数量。【数据规模】【数据规模】对于对于100%的数据：的数据：n=1000。第57页，本讲稿共169页58【样例输入输出】bumb.inbumb.out82 7 1 9 10 1 2 34题意简述：题意简述：给定给定n个元素的数列，求最长的上升子序列长度。个元素的数列，求最长的上升子序列长度。即：在原序列中，最多能选多少个数，在原有

25、顺序即：在原序列中，最多能选多少个数，在原有顺序下递增。下递增。第58页，本讲稿共169页最长上升子序列长度（最长上升子序列长度（LISLIS）：）：59最长上升子序列显然是以某一个最长上升子序列显然是以某一个aiai作为第一元素的一作为第一元素的一个最长上升子序列。个最长上升子序列。如果求出以原序列中每一个元素如果求出以原序列中每一个元素aiai作为第一个元素作为第一个元素开头的最长上升子序列长度开头的最长上升子序列长度fi.fi.那么那么:ans=maxfi:ans=maxfi；i=1.ni=1.n问题是怎么求问题是怎么求fi?fi?8 2 7 1 9 10 1 4 3第59页，本讲稿共1

26、69页倒推法：倒推法：60ai:数列中的第数列中的第i个数。个数。fi:以以ai为开始为开始(ai是被选中的第一个元素是被选中的第一个元素)的最长递的最长递增子序列的序列长度。增子序列的序列长度。转移方程：转移方程：fi=maxfj+1 条件：条件：ij=n并且并且aiaj边界：边界：fn=1;目标：目标：maxfi;1=iai)and(fjfi)then fi:=fj;/找最大的找最大的fj inc(fi);/包含包含ai end;ans:=f1;for i:=2 to n do if fians then ans:=fi;writeln(ans);第61页，本讲稿共169页顺推：顺推：62

27、ai:数列中的第i个数。fi:以ai为结尾(ai是被选中的最后一个元素)的最长递增子序列的序列长度。fi=maxfj+1fi=maxfj+1 条件：条件：1=ji1=ji并且并且ajaiajai边界：边界：f1=1;f1=1;目标：目标：maxfi;1=i=nmaxfi;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

28、i:=2 to n do if fians then ans:=fi;writeln(ans);第63页，本讲稿共169页最长上升子序列长度（最长上升子序列长度（LISLIS）：）：64 倒推：fi:以ai为开始元素的最长递增子序列的序列长度。转移方程：fi=maxfj+1 条件：ij=n并且aiaj边界：fn=1;目标：maxfi;1=i=n第64页，本讲稿共169页顺推：顺推：65fi:以以ai为结尾为结尾的最长递增子序列的序列长度。的最长递增子序列的序列长度。fi=maxfj+1 条件：1=ji并且ajai边界：f1=1;目标：maxfi ;1=i=n时间复杂度：时间复杂度：O(n2)第

29、65页，本讲稿共169页知识扩展：知识扩展：66最长上升子序列长度；最长上升子序列长度；最长不下降子序列长度；最长不下降子序列长度；最长不上升子序列长度。最长不上升子序列长度。=第66页，本讲稿共169页例例2 2：合唱队形：合唱队形 NOIP 2004 NOIP 200467【问题描述】【问题描述】N位同学站成一排，音乐老师要请其中的位同学站成一排，音乐老师要请其中的(N-K)位同学出列，位同学出列，使得剩下的使得剩下的K位同学排成合唱队形。位同学排成合唱队形。合唱队形是指这样的一种队形：设合唱队形是指这样的一种队形：设K 位同学从左到右依次位同学从左到右依次编号为编号为1，2，K，他们的身

30、高分别为，他们的身高分别为T1,T2,Tk,则他们的身高满足则他们的身高满足T1T2Ti+1Tk(1=i=K)。你的任务是：你的任务是：已知有已知有N位同学的身高，计算位同学的身高，计算最少最少需要几位同学出列，可以使需要几位同学出列，可以使得剩下的同学排成合唱队形。得剩下的同学排成合唱队形。第67页，本讲稿共169页68【样例输入输出样例输入输出】chorus.inchorus.out8186 186 150 200 160 130 197 2204【输入】【输入】第一行是一个整数第一行是一个整数N(2=N=1000),表示同学的总数。表示同学的总数。第二行有第二行有n个整数，用空格分隔，第

31、个整数，用空格分隔，第i个整数个整数Ti(130=Ti=230)是第是第i位同学的身高（厘米）。位同学的身高（厘米）。【输出】【输出】一个整数，表示最少需要几位同学出列。一个整数，表示最少需要几位同学出列。【数据规模】【数据规模】对与全部的数据，保证有对与全部的数据，保证有n=1000。第68页，本讲稿共169页问题分析问题分析:69计算计算最少最少需要几位同学需要几位同学出列出列，可转化为计算，可转化为计算最多能留下最多能留下多少同多少同学。学。将所有合唱队形同学排为一列，在二维坐标系中根据身高描点将所有合唱队形同学排为一列，在二维坐标系中根据身高描点连线，图样就像一座山峰。连线，图样就像一

32、座山峰。队列左边的身高依次上升，右边依次下降，队列左边的身高依次上升，右边依次下降，中间有一个最高点中间有一个最高点，而这个最高点的左侧是上升子序列，右侧是下降子序列。人数最多而这个最高点的左侧是上升子序列，右侧是下降子序列。人数最多是最优合唱队形。是最优合唱队形。第69页，本讲稿共169页算法描述：算法描述：70对整个身高序列对整个身高序列ai做：做：一次最长上升子序列一次最长上升子序列(fi)：正推求；：正推求；一次最长下降子序列一次最长下降子序列(gi)：倒推求；：倒推求；之后枚举最高点之后枚举最高点ai:ans=max(fi+gi-1)是保留最大值。是保留最大值。最少出队列人数最少出队

33、列人数:n-ans.第70页，本讲稿共169页参考代码：参考代码：71ai:ai:身高。身高。fi:fi:以以aiai为最后一个人最长上升子序列长度为最后一个人最长上升子序列长度 f1:=1;f1:=1;for i:=2 to n dofor i:=2 to n do begin begin for j:=1 to i-1 do for j:=1 to i-1 do if(ajfi)if(ajfi)then fi:=fj;then fi:=fj;inc(fi);inc(fi);end;end;第71页，本讲稿共169页72/gi:/gi:以以aiai开头的最长下降子序列长度开头的最长下降子序列

34、长度gn:=1;gn:=1;for i:=n-1 downto 1 dofor i:=n-1 downto 1 do begin begin for j:=i+1 to n do for j:=i+1 to n do if(ajgi)if(ajgi)then gi:=gj;then gi:=gj;inc(gi);inc(gi);end;end;第72页，本讲稿共169页枚举以第枚举以第i i位同学为最高的队形：位同学为最高的队形：73ans:=0;/ans:=0;/保留的最多人数。保留的最多人数。for i:=1 to n dofor i:=1 to n do if fi+gi-1ans if

35、 fi+gi-1ans then ans:=fi+gi-1;then ans:=fi+gi-1;writeln(n-ans);/writeln(n-ans);/最少出队人数最少出队人数第73页，本讲稿共169页例例3 3：上帝选人：上帝选人74【问题描述】【问题描述】世界上的人都有世界上的人都有智商智商IQ和和情商情商EQ。我们用两个数字来表示人的智。我们用两个数字来表示人的智商和情商，数字大就代表其相应智商或情商高。现在你面前有商和情商，数字大就代表其相应智商或情商高。现在你面前有N个人，个人，这这N个人的智商和情商均已知，请你选择出尽量多的人，要求个人的智商和情商均已知，请你选择出尽量多的

36、人，要求选出的人中不存在任意两人选出的人中不存在任意两人i和和j，i的智商大于的智商大于j的智商但的智商但i的情商小的情商小于于j的情商。的情商。【输入】【输入】第一行一个正整数第一行一个正整数N，表示人的数量。，表示人的数量。第二行至第第二行至第N+1行，每行两个正整数，分别表示每个人的智商和情行，每行两个正整数，分别表示每个人的智商和情商。商。【输出】【输出】仅一行，为最多选出的人的个数。仅一行，为最多选出的人的个数。第74页，本讲稿共169页75【数据规模和约定】【数据规模和约定】N iqj iqi iqj），但），但(eqi eqj)(eqi=IQj)and(EQi=EQj)(IQi=

37、IQj)and(EQi=EQj)或者或者(IQi=IQj)and(EQi=EQj)(IQi=IQj)and(EQi=EQj)第76页，本讲稿共169页再形象一点：再形象一点：7780901002507085100 120第77页，本讲稿共169页78对于所有选出的人：对于所有选出的人：当当IQ有序时，有序时，EQ必定是有序的（连线不相交）。必定是有序的（连线不相交）。同序同序80901002507085100120第78页，本讲稿共169页79IQ EQ10 269 2112 198 15IQ EQ8 159 2110 2612 19第79页，本讲稿共169页80IQ EQ11 510 610

38、 610 5IQ EQ10 510 610 611 5第80页，本讲稿共169页设计算法：设计算法：811.将所有人将所有人IQ（或者（或者EQ）从小到大排序。）从小到大排序。2.求求EQ（或者（或者IQ）的最长非递减子序列长度）的最长非递减子序列长度.第81页，本讲稿共169页例例4 4：递增子序列最大和：递增子序列最大和82【问题描述】【问题描述】给定长度为给定长度为n的的正正整数序列整数序列a1,a2,an。求一个递增的子序列，和最大。求一个递增的子序列，和最大。【输入】【输入】第一行，第一行，n，表示给定序列的个数。，表示给定序列的个数。第二行，第二行，n个用空格隔开的正整数。个用空格

39、隔开的正整数。【输出】【输出】递增子序列的最大和。递增子序列的最大和。【数据范围限制】【数据范围限制】n=1000,0ai=109。第82页，本讲稿共169页83【输入输出样例输入输出样例】Sum.inSum.out62 4 1 20 5 626递增的子序列最大和：递增的子序列最大和：2+4+20=26。不是最长递增子序列不是最长递增子序列LIS而是简单变形！而是简单变形！第83页，本讲稿共169页算法描述：算法描述：84定义定义fi表示以表示以 ai 为最后一个数的递增子序列的为最后一个数的递增子序列的最大和。最大和。2 4 1 20 5 6fi:=max(fj)+ai （1=ji且且aja

40、i）Ans=maxfi i=1.n时间：时间：O(n*n)第84页，本讲稿共169页参考代码：参考代码：85f1:=a1;ans:=0;f1:=a1;ans:=0;for i:=2 to n dofor i:=2 to n do begin begin for j:=1 to i-1 do for j:=1 to i-1 do if(ajai)then if(ajans then ans:=fi;for i:=1 to n do if fians then ans:=fi;writeln(ans);writeln(ans);第85页，本讲稿共169页2 2：最大连续子序列的和模型：最大连续子序

41、列的和模型86求给定序列的最大连续子序列和。求给定序列的最大连续子序列和。输入：第一行：输入：第一行：n（nans then ans:=sum;if sumans then ans:=sum;end;end;writeln(ans);writeln(ans);时间：时间：O(n3)第87页，本讲稿共169页88算法算法2 2：算法：算法1 1的稍加改进的稍加改进 ans:=-300000000;ans:=-300000000;for i:=1 to n do for i:=1 to n do begin begin sum:=0;sum:=0;for j:=i to n do for j:=i

42、 to n do begin begin sum:=sum+aj;sum:=sum+aj;if sumans then ans:=sum;if sumans then ans:=sum;end;end;end;end;writeln(ans);writeln(ans);时间：时间：O(n2)第88页，本讲稿共169页891 1、以、以aiai为结束点和以为结束点和以ai-1ai-1为结束点的最大连续为结束点的最大连续子序列和有没有联系？子序列和有没有联系？有什么样的联系？有什么样的联系？2 2、如果事先已经求得了以、如果事先已经求得了以ai-1ai-1为结束点的最大连为结束点的最大连续子序列和

43、为续子序列和为x x，那么怎样求以，那么怎样求以aiai为结束点的最大连为结束点的最大连续子序列？续子序列？-6 4 -1 3 2 -3 2继续分析：继续分析：第89页，本讲稿共169页90ai:序列；序列；fi：以：以ai为终点（连续区间的右边界）的子序列为终点（连续区间的右边界）的子序列的最大和。的最大和。时间：时间：O(n)顺推法：顺推法：fi=maxfi-1+ai,ai fi=maxfi-1+ai,ai =maxfi-1,0+ai =maxfi-1,0+ai初始：初始：f1=a1f1=a1目标：目标：maxfi (1=i=n)maxfi (1=ians then ans:=fi;if

44、fians then ans:=fi;第91页，本讲稿共169页92ai:ai:序列；序列；fi:fi:从第从第i i项开始项开始(以第以第i i项为第项为第1 1项项)的最大连续子序列的和。的最大连续子序列的和。fi=maxfi+1+ai,ai fi=maxfi+1+ai,ai 初始：初始：fn=anfn=an目标：目标：maxfi 1=i=nmaxfi 1=ians then ans:=fi;第93页，本讲稿共169页94ans:=0;s:=0;for i:=1 to n do begin s:=s+ai;if sans then ans:=s;end;writeln(ans);进一步分析

45、上面的两种求解方法，新序列要么是在现有某序列的一端添加一个元素，要么是只包含该元素。第94页，本讲稿共169页例例6 6：勤工俭学（下午上机题目）：勤工俭学（下午上机题目）95f0:=0;d0:=0;for i:=1 to n do begin if fi-10 then begin fi:=fi-1+ai;di:=di-1+1;end else begin fi:=ai;di:=1;end;end;第95页，本讲稿共169页3.最长公共子序列问题最长公共子序列问题 LCS96 最长公共子序列也称作最长公共子串最长公共子序列也称作最长公共子串(不要不要求一定连续求一定连续)，英文缩写为，英文缩

46、写为LCSLCS（Longest Common Longest Common SubsequenceSubsequence）。）。其定义是，一个序列其定义是，一个序列 S S，如果分别是两个或，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列多个已知序列的子序列，且是所有符合此条件序列中最长的，则中最长的，则 S S 称为已知序列的最长公共子序称为已知序列的最长公共子序列。列。第96页，本讲稿共169页97给定两个序列给定两个序列X=x1,x2,.,xm Y=y1,y2,.,yn 求求X和和Y的一个最长公共子序列的一个最长公共子序列举例举例X=a,b,c,b,d,a,b Y=b,d

47、,c,a,b,a 最长公共子序列为最长公共子序列为LSC=b,c,b,a 例例7：第97页，本讲稿共169页98要求：要求：X和和Y以字符串输入，长度以字符串输入，长度=1000.输出：最长公共子串的长度输出：最长公共子串的长度如：如：输入：输入：a abcbbcbd da ab bb bd dc ca ababa输输出出4 4LCS=bcbaLCS=bcba第98页，本讲稿共169页分析：分析：99X=abcdefghY=acnehX=abcdefghY=acnehkX=abcdefgkhY=acnehkX=abcdefgnY=acnem第99页，本讲稿共169页分析：分析：100X=xX=

48、x1 1,.,x,.,xi-1i-1 ，x xi i Y=yY=y1 1,.,y,.,yj-1j-1 ，y yj j fi,j:xfi,j:x的前的前i i个和个和y y的前的前j j个字符的最大公共子序列长度。个字符的最大公共子序列长度。xi=yj xi=yj 时时 ,fi,j=fi-1,j-1+1,fi,j=fi-1,j-1+1xi yjxi yj时时 ,fi,j=max fi,j-1,fi,j=max fi,j-1,fi-1,j fi-1,j 第100页，本讲稿共169页参考代码：参考代码：101for i:=1 to n do for i:=1 to n do /X/X的长度的长度 f

49、or j:=1 to m do for j:=1 to m do /Y/Y的长度的长度 begin begin fi,j:=0;fi,j:=0;if xi=yj then fi,j:=fi-1,j-1+1 if xi=yj then fi,j:=fi-1,j-1+1 else fi,j:=else fi,j:=maxmax(fi-1,j,fi,j-1);(fi-1,j,fi,j-1);end;end;第101页，本讲稿共169页（二）坐标类模型（二）坐标类模型102比较简单的一类动态规划问题。比较简单的一类动态规划问题。常以二维空间坐标系为模板展开，因此状态转移常以二维空间坐标系为模板展开，因

50、此状态转移方程也在坐标系中寻找，方程也在坐标系中寻找，一般定义一般定义fi,j表示状态，此状态表示某个点的坐表示状态，此状态表示某个点的坐标。标。有关系的状态：有关系的状态：fi-1,j，fi,j-1，fi-1,j-1按行或列的顺序求解问题。按行或列的顺序求解问题。第102页，本讲稿共169页引例引例1 1：数字三角形【：数字三角形【IOI 1994IOI 1994】有一个数字三角形，从最顶层出发，每一步只能向左下有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。下图数