《动态规划基础PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《动态规划基础PPT讲稿.ppt（89页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划基础动态规划基础第1页，共89页，编辑于2022年，星期五内容内容:引例引例动态规划的概念与原理动态规划的概念与原理例题分析例题分析第2页，共89页，编辑于2022年，星期五 一个含有一个含有n阶的楼梯，一次可以走阶的楼梯，一次可以走1步或步或2步，从底走步，从底走到顶一共有几种走法？到顶一共有几种走法？3=n=90。(4660046610375530309:qword)一、引例一、引例【引例、上楼梯引例、上楼梯】f(1)=1f(2)=2f(n)=f(n-1)+f(n-2)第3页，共89页，编辑于2022年，星期五varvar n:integer;/n=90 n:integer;/n0
2、 then exit(fi);if fi0 then exit(fi);dp:=dp(i-1)+dp(i-2);dp:=dp(i-1)+dp(i-2);fi:=dp;fi:=dp;end;end;BeginBegin fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);readln(n);readln(n);writeln(dp(n);writeln(dp(n);end.end.第5页，共89页，编辑于2022年，星期五思考：思考：1 1、算法算法1 1与与算法算法2 2那个更好？那个更好？2 2、为什么？、为什么？第6页，共89页，编辑于2022年
3、，星期五f6f5f3f2f1f3f2f1f4f2f3f2f1f3f2f1f4f2f3f2f1f(1)=1;f(2)=2f(n)=f(n-1)+f(n-2)算法算法1：第7页，共89页，编辑于2022年，星期五f6f5f3f2f1f3f2f1f4f2f3f2f1f3f4f(1)=1;f(2)=2f(n)=f(n-1)+f(n-2)算法算法2 2：第8页，共89页，编辑于2022年，星期五算法算法3 3：constconst maxn=90;maxn=90;varvar n:integer;n:integer;f:array1.maxn of qword;f:array1.maxn of qwor
4、d;procedure dp(i:integer);procedure dp(i:integer);begin begin if i=1 then begin fi:=1;exit;end;if i=1 then begin fi:=1;exit;end;if i=2 then begin fi:=2;exit;end;if i=2 then begin fi:=2;exit;end;if fi0 then exit;if fi0 then exit;dp(i-1);dp(i-1);dp(i-2);dp(i-2);fi:=fi-1+fi-2;fi:=fi-1+fi-2;end;end;begi
5、nbegin readln(n);readln(n);dp(n);dp(n);writeln(fn);writeln(fn);end.end.第9页，共89页，编辑于2022年，星期五算法算法4 4：constconst maxn=90;maxn=90;varvar n:integer;n:integer;f:array1.maxn of qword;f:array1.maxn of qword;procedure dp;procedure dp;var i:integer;var i:integer;begin begin f1:=1;f2:=2;f1:=1;f2:=2;for i:=3 t
6、o n do fi:=fi-1+fi-2;for i:=3 to n do fi:=fi-1+fi-2;end;end;beginbegin readln(n);readln(n);dp;dp;writeln(fn);writeln(fn);end.end.第10页，共89页，编辑于2022年，星期五算法算法5 5：varvar n,i:integer;n,i:integer;a,b,c:qword;a,b,c:qword;beginbegin readln(n);readln(n);a:=1;b:=2;a:=1;b:=2;for i:=1 to n-2 do for i:=1 to n-2
7、do begin begin c:=a+b;c:=a+b;a:=b;a:=b;b:=c;b:=c;end;end;writeln(c);writeln(c);end.end.第11页，共89页，编辑于2022年，星期五算法算法2 2算法算法5 5：重复的部分只计算重复的部分只计算一一次次第12页，共89页，编辑于2022年，星期五【引例引例2 2、数字三角形、数字三角形(IOI94)(IOI94)】有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路上数字之和的最大值。
8、每一步只能向左下或右下方向走。下图数据的路应为应为7-3-8-7-57-3-8-7-5，和为，和为3030。输入：输入：第一行：第一行：R(1=R=100),R(1=R=100),数字三角形共有数字三角形共有R R行；行；以下以下R R行：依次表示数字三角形中每行中的数字。行：依次表示数字三角形中每行中的数字。每个数都是非负的，且每个数都是非负的，且=100.max then max:=sum;exit;end;dfs(sum+ai+1,j,i+1,j);向左下方走向左下方走 dfs(sum+ai+1,j+1,i+1,j+1);向右下方走向右下方走 end;开始时：开始时：dfs(a1,1,1
9、,1);结果：结果：max为什么当为什么当n n较大时速度慢？较大时速度慢？7 3 8 8 1 0 2 7 4 44 5 2 6 5第14页，共89页，编辑于2022年，星期五算法算法2 2：/f:array0.100,0.100 of integer;/f:array0.100,0.100 of integer;/fI,j/fI,j:(I,j):(I,j)到最后一行的最大值到最后一行的最大值function max(a,b:longint):longint;function max(a,b:longint):longint;begin begin if ab then exit(a)else
10、 exit(b);if ab then exit(a)else exit(b);end;end;Procedure dfs(i,j:integer);/Procedure dfs(i,j:integer);/求求(i,j)(i,j)到最后一行的最大和到最后一行的最大和 beginbegin if i=n then if i=n then begin fi,j:=ai,j;exit;end;begin fi,j:=ai,j;exit;end;if fi,j0 then exit;if fi,j0 then exit;dfs(i+1,j);dfs(i+1,j);dfs(i+1,j+1);dfs(i
11、+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;BeginBegin init;init;dfs(1,1);dfs(1,1);writeln(f1,1);writeln(f1,1);End.End.7 3 8 8 1 0 2 7 4 44 5 2 6 5第15页，共89页，编辑于2022年，星期五方法方法1：从最后一行向起点走：从最后一行向起点走/逆向逆向设设FI,j:ai,j到达第到达第n行行an,k（k：1-n）的最大值）的最大值递推关系：递推关系：fi,j=maxfi+1,j,
12、fi+1,j+1+aI,j初始：初始：fn,i:=an,i;1=imax then max:=b;end;第17页，共89页，编辑于2022年，星期五方法方法2：依次求从起点：依次求从起点(1,1)到点（到点（i，j）的最大值。）的最大值。/正向正向设设FI,j为从为从a1,1到达到达aI,j时取得的最大值时取得的最大值根据题意可得出递推关系：根据题意可得出递推关系：fi,j=maxfi-1,j-1,fi-1,j+aI,j初始：初始：f1,1:=a1,1;目标：目标：maxfn,i 1=ians then ans:=fn,i;writeln(ans);end;第19页，共89页，编辑于2022
13、年，星期五思考：算法1与算法2和算法3的主要区别在哪里？算法算法1：每求一条从起点到终点的路线，中间的点都重新求：每求一条从起点到终点的路线，中间的点都重新求一遍。做了大量的重复性计算。一遍。做了大量的重复性计算。算法算法2、3：中间结点的值只求一次，后边的点可以直：中间结点的值只求一次，后边的点可以直接使用前边以求得的值。接使用前边以求得的值。第20页，共89页，编辑于2022年，星期五【引例引例3：求最大连续子序列的和。：求最大连续子序列的和。】输入：第一行：输入：第一行：n（Nans then ans:=sum;if sumans then ans:=sum;end;end;writel
14、n(ans);writeln(ans);时间：时间：O(n3)理想的算法：理想的算法：ans then ans:=sum;if sumans then ans:=sum;end;end;end;end;writeln(ans);writeln(ans);时间：时间：O(nO(n2 2)第23页，共89页，编辑于2022年，星期五算法算法1 1和算法和算法2 2是把是把n n个数看作独立的没有联系个数看作独立的没有联系的数来处理的。的数来处理的。1、以、以ai为结束点和以为结束点和以ai+1为结束点的最大连续子序列为结束点的最大连续子序列有没有联系？有没有联系？有什么样的联系？有什么样的联系？2
15、、如果事先已经求得了以、如果事先已经求得了以ai为结束点的最大连续为结束点的最大连续子序列和为子序列和为x，那么怎样求以，那么怎样求以ai+1为结束点的最大为结束点的最大连续子序列？连续子序列？-64-132-32第24页，共89页，编辑于2022年，星期五分析分析1：Ai:存储序列；存储序列；Fi：从第：从第1项开始，以项开始，以ai为终点（右边界）的子序列的最大和。为终点（右边界）的子序列的最大和。fi=maxfi-1+ai,ai：即看即看fi-1的正负的正负初始：初始：f1=a1目标：目标：maxfi 1=ians then ans:=fi;end;时间：时间：O(n)第25页，共89页
16、，编辑于2022年，星期五分析分析2：Ai:存储序列；存储序列；Fi：从第：从第i项开始项开始以第以第i项为第一项项为第一项的最大连续子序列的和。的最大连续子序列的和。fi=maxfi+1+ai,ai：即看即看fi-1的正负的正负初始：初始：fn=an目标：目标：maxfi 1=ians then ans:=fi;end;-64-132-32第26页，共89页，编辑于2022年，星期五1、动态规划（、动态规划（DP）：）：DynamicProgramming基本思想：基本思想：把问题分解为求若干子问题，先求出子问题的解，然后通过组把问题分解为求若干子问题，先求出子问题的解，然后通过组合子问题的
17、解来解决整个问题的解。合子问题的解来解决整个问题的解。这些子问题不是独立的，各子问题包含有公共的这些子问题不是独立的，各子问题包含有公共的子子问题子子问题。Dp是把公共是把公共的子问题的子问题只求解一次只求解一次，并把结果保存记录下来，供后面使用。，并把结果保存记录下来，供后面使用。二、动态规划的基本原理二、动态规划的基本原理第27页，共89页，编辑于2022年，星期五Dp通常应用于最优化问题：通常应用于最优化问题：这类问题有很多的可行解，我们希望找出最优的一个解这类问题有很多的可行解，我们希望找出最优的一个解（最大或最小），称这样的解为问题的（最大或最小），称这样的解为问题的“一个一个”最优
18、解，因最优解，因为可能存在多个最优解。为可能存在多个最优解。第28页，共89页，编辑于2022年，星期五2、动态规划问题的特征：、动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的动态规划算法的有效性依赖于问题本身所具有的3个重要性质：个重要性质：“最优子结最优子结构构”性质和性质和“子问题重叠子问题重叠”性质以及性质以及“无后效性原则无后效性原则”。1）、）、最优子结构最优子结构：当问题的最优解包含了其子问题的最优解时，称该：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。也称最优化原理。问题具有最优子结构性质。也称最优化原理。“整体最优则局部最优。整体最优则
19、局部最优。”反之不一定成立反之不一定成立2）、）、重叠子问题重叠子问题：（在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有（在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。）些子问题被反复计算多次。）动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。第29页，共89页，编辑于2022年，星期五3）、）、无后效性原则无后效性原则：
20、“已经求得的状态值，不受未求的那些状态的影响已经求得的状态值，不受未求的那些状态的影响”结合：数字三角形，最大连续子序列和结合：数字三角形，最大连续子序列和第30页，共89页，编辑于2022年，星期五一个问题满足最优化原理：一个问题满足最优化原理：子问题的性质：子问题的性质：1）、子问题可以递归的求解。）、子问题可以递归的求解。2）、这些子问题是有重叠的，即有些子问题需要求解多）、这些子问题是有重叠的，即有些子问题需要求解多次。次。如果符合上述条件我们可以考虑使用动态规划的方式高如果符合上述条件我们可以考虑使用动态规划的方式高效的求解。把子问题及其解记录下来，同样的子问题只求解效的求解。把子问
21、题及其解记录下来，同样的子问题只求解一次，从而大大的提高了效率。一次，从而大大的提高了效率。第31页，共89页，编辑于2022年，星期五3、动态规划求解、动态规划求解动态规划以动态规划以“自底向上自底向上”的方式来利用最优子结构：首先找到子的方式来利用最优子结构：首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。寻找问问题的最优解，解决子问题，然后找到问题的一个最优解。寻找问题的一个最优解需要在子问题中做出选择，即选择哪一个来求解问题的一个最优解需要在子问题中做出选择，即选择哪一个来求解问题。问题解的代价是子问题的代价加上选择本身带来的开销。题。问题解的代价是子问题的代价加上选择本
22、身带来的开销。“先解决子问题，再做选择先解决子问题，再做选择”Dp的编程实现方法：的编程实现方法：1）、递归（记忆化搜索），直接。在递归求解时，先判断该子问）、递归（记忆化搜索），直接。在递归求解时，先判断该子问题是否求过，如果求过，就直接返回之前记录下来的解，否则再递题是否求过，如果求过，就直接返回之前记录下来的解，否则再递归的求解，并在最后保存这个解，以后备用。归的求解，并在最后保存这个解，以后备用。2）、递推：先求小的子问题，再计算大的子问题，最终把目标问题解决。）、递推：先求小的子问题，再计算大的子问题，最终把目标问题解决。关键：在求某个子问题时，他需要用的子问题都必须是已经求解了的，
23、否关键：在求某个子问题时，他需要用的子问题都必须是已经求解了的，否则有可能出错。正推则有可能出错。正推，逆推，逆推第32页，共89页，编辑于2022年，星期五“贪心算法贪心算法“：和和dp很相似，它使用的问题也具有最优子结构。很相似，它使用的问题也具有最优子结构。显著区别：贪心采用的显著区别：贪心采用的“自顶向下自顶向下”的方式使用最优子结构的。贪的方式使用最优子结构的。贪心算法：先做选择，在当时看起来是最优的选择（只顾眼前利益），然后心算法：先做选择，在当时看起来是最优的选择（只顾眼前利益），然后再求一个结果子问题，而不是和再求一个结果子问题，而不是和dp一样：先寻找子问题的解，然后做一样：
24、先寻找子问题的解，然后做出选择。出选择。“先选择，再求解子问题先选择，再求解子问题”7 3 8 8 1 0 2 7 4 44 5 2 6 5第33页，共89页，编辑于2022年，星期五动态规划的术语：动态规划的术语：1、阶段：阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用为阶段变量。在多数情况下，阶段变量是离散的，用k k表示。表示。阶段的划分一般根据
25、时间和空间来划分的。阶段的划分一般根据时间和空间来划分的。2、状态：、状态：某一阶段的出发位置成为状态，通常一个阶段有多个状态。某一阶段的出发位置成为状态，通常一个阶段有多个状态。状态通常可以用一个或一组数来描述，称为状态变量。状态通常可以用一个或一组数来描述，称为状态变量。3、决策：、决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。选择（行动）称为决策。描述决策的变量称决策变量描述决策的变量称决策变量 4、策略和最优策略、策略和最优策略 所有阶段的决策有序组合构成一个策略。所有阶段的决策有序组
26、合构成一个策略。最优效果的策略叫最优策略。最优效果的策略叫最优策略。第34页，共89页，编辑于2022年，星期五例：最短路径问题例：最短路径问题 现在，我们想从城市现在，我们想从城市A A到达城市到达城市E E。怎样走才能使得路径最短，最短路径的长度是多少？怎样走才能使得路径最短，最短路径的长度是多少？AB1B2C1C2C3C4D1D2D3E531638438556343第35页，共89页，编辑于2022年，星期五用倒推法（从后向前）用倒推法（从后向前）A A到到E E的最短距离的最短距离:用用k表示阶段，按路径选择的策略划分，共有表示阶段，按路径选择的策略划分，共有4个阶段：个阶段：第第1阶
27、段：阶段：1个初始状态（起点）个初始状态（起点）A，终点，终点B1,B2第第2阶段：阶段：2个初始状态（起点）个初始状态（起点）B1,B2，终点，终点:C1,C2,C3,C4第第3阶段：阶段：4个初始状态（起点）个初始状态（起点）C1,C2,C3,C4，终点，终点:D1,D2,D3第第4阶段：阶段：3个初始状态（起点）个初始状态（起点）D1,D2,D3，终点，终点:EAB1B2C1C2C3C4D1D2D3E531638438556343阶段阶段1阶段阶段2阶段阶段3阶段阶段4第36页，共89页，编辑于2022年，星期五用用dk(xk,xk+1)表示在第表示在第k阶段由初始状态阶段由初始状态xk
28、到下一阶段的初始状态到下一阶段的初始状态xk+1的距的距离。离。用用Fk(xk)表示从第表示从第k阶段的状态阶段的状态xk到终点到终点E的最短距离。的最短距离。K=5：F5(E)=0;K=4:F4(D1)=3;F4(D2)=4;F4(D3)=3K=3:F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)=min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=8 F3(C3)=d3(C3,D3)+F4(D3)=11 F3(C4)=d3(C4,D3)+F4(D3)=6K=2:F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F
29、3(C2),d2(B1,C3)+F3(C3)=min1+8,6+8,3+11=9 F2(B2)=mind2(B2,C2)+F3(C2),d2(B2,C4)+F3(C4)=min8+8,4+6=10K=1:F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min5+9,3+10=13最短路径：AB2C4D3E最短距离：13第37页，共89页，编辑于2022年，星期五AB1B2C1C2C3C4D1D2D3E531638438556343阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5也可以按照状态来划分阶段：第38页，共89页，编辑于2022年，星期五倒推法：倒推
30、法：f f5 5EE0 0；for kfor k4 downto 1 do 4 downto 1 do 枚举阶段枚举阶段 for x for x取遍取遍k k阶阶段的所有城市段的所有城市do do 枚举状态枚举状态 begin begin f fk kxx；for yfor y取遍取遍k+1k+1阶阶段的所有城市段的所有城市do do 枚举策略枚举策略 if f if fk+1k+1y+dy+dk kx,yfx,yfk kx x then f then fk kxxf fk+1k+1y+dy+dk kx,yx,y；endend；forfor输输出出f f1 1AA；第39页，共89页，编辑于2
31、022年，星期五状态转移方程：状态转移方程：前一阶段的终点是后一阶段的起点，对前一阶段的状态作出某种决策前一阶段的终点是后一阶段的起点，对前一阶段的状态作出某种决策产生后一阶段的状态，这种描述产生后一阶段的状态，这种描述k-1k-1阶段到阶段到k k阶段状态的变化规律称为状态转移阶段状态的变化规律称为状态转移方程。方程。fkx=minfk-1yi+dk-1yi,x (顺推顺推)顺推：fUk=optfUk-1+LUk-1,Xk-1 （LUk-1,Xk-1：状态：状态Uk-1通过策略通过策略Xk-1到达状态到达状态Uk 的费用）的费用）初始初始fU1；结果：；结果：f(Un)倒推：fUk=optf
32、Uk+1+LUk,Xk （LUk,Xk：状态：状态Uk通过策略通过策略Xk到达状态到达状态Uk+1 的费用）的费用）初始初始fUn；结果：；结果：f(U1)一般形式：一般形式：U：状态；X：策略：策略第40页，共89页，编辑于2022年，星期五AB1B2C1C2C3C4D1D2D3E531638438556343阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5最优子结构、重叠子问题、无后效性最优子结构、重叠子问题、无后效性第41页，共89页，编辑于2022年，星期五不具备无后效性原则：不具备无后效性原则：倒推时：第倒推时：第3 3阶段的状态阶段的状态C1C1到到E E的距离受到第二阶段的的距
33、离受到第二阶段的状态状态B1B1的影响的影响2AB1B2C1C2C3C4D1D2D3E531638438556343阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5第42页，共89页，编辑于2022年，星期五设计动态规划法的步骤：设计动态规划法的步骤：1、找出最优解的性质，并刻画其结构特征；、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；、以自底向上的方式计算出最优值；记忆化搜索（树型）、记忆化搜索（树型）、递推递推4、根据计算最优值时得到的信息，构造一个最优解。、根据计算最优值时得到的
34、信息，构造一个最优解。第43页，共89页，编辑于2022年，星期五动态规划的动态规划的一般倒推一般倒推程序程序格式格式为为：fUfUn n=初始值；初始值；for kfor kn downto 1 do n downto 1 do 枚举阶段枚举阶段 for Ufor U取遍所有状取遍所有状态态 do do 枚举状态枚举状态 for X for X取遍所有决策取遍所有决策 do do 枚举决策枚举决策 fUfUk k=optfU=optfUk+1k+1+LU+LUk k,X,Xk k；LU LUk k,X,Xk k：状态：状态U Uk k通过策略通过策略X Xk k到达状到达状态态U Uk+1
35、k+1 的的费费用用 输输出：出：fUfU1 1:目目标标第44页，共89页，编辑于2022年，星期五动态规划的动态规划的一般一般顺顺推推程序程序格式格式为为：fUfU1 1=初始值；初始值；for kfor k1 to n do 1 to n do 枚举每一个阶段枚举每一个阶段 for Ufor U取遍所有状取遍所有状态态 dodo for X for X取遍所有决策取遍所有决策 dodo fUfUk k=optfU=optfUk-1k-1+LU+LUk-1k-1,X,Xk-1k-1；LU LUk-1k-1,X,Xk-1k-1：状态：状态U Uk-1k-1通过策略通过策略X Xk-1k-1到
36、达状到达状态态U Uk k 的的费费用用 输输出：出：fUfUn n:目目标标第45页，共89页，编辑于2022年，星期五1、最长递增序列、最长递增序列问题描述问题描述 设有整数序列设有整数序列b1,b2,b3,bm，若存在，若存在i1i2i3in，且，且bi1bi2bi3bin，则称，则称 b1,b2,b3,bm中有长度为中有长度为n的递增序列的递增序列bi1,bi2,bi3,bin。求序列。求序列b1,b2,b3,bm中最大递增序列长度中最大递增序列长度(n)。输入：输入：m（1000）,整数序列整数序列输出：最大长度输出：最大长度n样例：样例：输入：输入：82 7 1 9 10 1 2
37、3输出：输出：4三、动态规划举例三、动态规划举例第46页，共89页，编辑于2022年，星期五分析分析1：从前往后：从前往后ai:保存数列的第保存数列的第i个数。个数。fi:以以ai为结尾为结尾(ai是最后一个元素是最后一个元素,即包含即包含ai)的最长递的最长递增子序列的序列长度。增子序列的序列长度。输入：输入：2 7 1 9 10 1 2 3第47页，共89页，编辑于2022年，星期五fi=maxfj+1 条件：条件：1=ji并且并且ajai边界：边界：f1=1;目标：目标：maxfi ;1=i=n输入：输入：82 7 1 9 10 1 2 3输出：输出：4fi:1 2 1 3 4 1 2
38、3第48页，共89页，编辑于2022年，星期五 f1:=1;max:=f1;for i:=2 to n do begin for j:=1 to i-1 do if(ajfi)then fi:=fj;找最大的找最大的fj fi:=fi+1;如果前边没有比如果前边没有比ai大的则大的则fi=1否则为否则为fi+1 if maxfi then max:=fi;end;writeln(max);close(input);end.第49页，共89页，编辑于2022年，星期五分析分析2：从后往前：从后往前Ai:保存数列的第保存数列的第i个数。个数。Fi:以以ai为开始为开始(ai是第一个元素是第一个元素
39、,即包含即包含ai)的最长递增子序列的最长递增子序列的序列长度。的序列长度。Fi=maxfj+1 条件：条件：ij=n并且并且aiaj边界：边界：fn=1;目标：目标：maxfi ;1=i=n2 7 1 9 10 1 2 3第50页，共89页，编辑于2022年，星期五Fi:以以 i为起始点的不下降序列长度。为起始点的不下降序列长度。fillchar(long,sizeof(long),0);fn:=1;max:=fn;for i:=n-1 downto 1 do begin for j:=i+1 to n do if(bifi)then fi:=fj;inc(fi);if fimax then
40、 max:=fi;end;第51页，共89页，编辑于2022年，星期五1、条件：、条件：最优化原理、重叠子问题、无后效性最优化原理、重叠子问题、无后效性2、概念：、概念：阶段、状态、策略阶段、状态、策略3、关键：、关键：动态转移方程（从简单开始找规律）动态转移方程（从简单开始找规律）初始化（根据实际意义，画表格）初始化（根据实际意义，画表格）边界、目标边界、目标4、空间与时间的优化：、空间与时间的优化：知识回顾知识回顾第52页，共89页，编辑于2022年，星期五AB1B2C1C2C3C4D1D2D3E531638438556343阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5第53页，共8
41、9页，编辑于2022年，星期五5 5、记住经典常用模型方程：、记住经典常用模型方程：fi=maxfi-1+ai,aifi=maxfi-1+ai,ai初始：初始：f1=a1f1=a1目标：目标：maxfi 1=i=nmaxfi 1=i=n1）、求最大连续子序列的和）、求最大连续子序列的和第54页，共89页，编辑于2022年，星期五2 2）、最长递增序列）、最长递增序列Fi:Fi:以以aiai为结尾为结尾(ai(ai是最后一个元素是最后一个元素,即包含即包含ai)ai)的最长递增子序列的序列长度。的最长递增子序列的序列长度。Fi=maxfj+1 Fi=maxfj+1 条件：条件：(1=ji)and
42、(ajai)(1=ji)and(ajai)边界：边界：f1=1;f1=1;目标：目标：maxfi ;1=i=nmaxfi ;1=i=n第55页，共89页，编辑于2022年，星期五1 1、拦截导弹、拦截导弹、拦截导弹、拦截导弹(noip1999)(noip1999)（daodan.pasdaodan.pas）【问题描述问题描述问题描述问题描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这
43、种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的
44、导于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。弹。弹。弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于输入导弹依次飞来的高度（雷达给出的高度数据是不大于输入导弹依次飞来的高度（雷达给出的高度数据是不大于输入导弹依次飞来的高度（雷达给出的高度数据是不大于3000030000的正整数），计的正整数），计的正整数），计的正整数），计算这套系统最多能拦截多少导弹？算这套系统最多能拦截多少导弹？算这套系统最多能拦截多少导弹？算这套系统最多能拦
45、截多少导弹？（导弹总个数不超过（导弹总个数不超过（导弹总个数不超过（导弹总个数不超过100100）样例：样例：样例：样例：【输入样例输入样例输入样例输入样例】daodan.indaodan.in8 83892071553002991701586538920715530029917015865【输出样例输出样例输出样例输出样例】daodan.outdaodan.out66例题例题:第56页，共89页，编辑于2022年，星期五解题思路：解题思路：本题实质是在一个数列中寻找一个递减的未必是连续的最长子序列。对于这个问题，我们可以从n出发，依次反向计算被拦截的导弹数。我们假设当导弹i作为被拦截的导弹之
46、一时，fi为导弹i到导弹n序列中可以被拦截的最多导弹数。对于fi的求解，我们可以这样考虑，对于所有的导弹j(i+1=j=n)，如果满足导弹j的高度小于等于导弹i的高度，则判断最大的fj得值，fi就是最大的fj+1，即：Fi:=maxfj(导弹j的高度=导弹i的高度)+1（i+1=j=n）for i:=1 to n do fi:=1;for i:=n-1 downto 1 do for j:=i+1 to n do if(mj=mi)and(fibest then best:=fi;writeln(best);主代码：主代码：第57页，共89页，编辑于2022年，星期五2 2、合唱队形合唱队形
47、N N位同学站成一排，音乐老师要请其中的位同学站成一排，音乐老师要请其中的(N-K)(N-K)位同学出列，使得剩下的位同学出列，使得剩下的K K位同学排成合唱队形。位同学排成合唱队形。合唱队形是指这样的一种队形：设合唱队形是指这样的一种队形：设K K位同学从左到右依次编号为位同学从左到右依次编号为1 1，22，K K，他们的身高分别为，他们的身高分别为T1T1，T2T2，TKTK，则他们的身高满足则他们的身高满足T1TK(1=i=K)T1TK(1=i=K)。你的任务是，已知所有你的任务是，已知所有N N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队位同学的身高，计算最少需
48、要几位同学出列，可以使得剩下的同学排成合唱队形。形。Input Input 第一行是一个整数第一行是一个整数N(2=N=100)N(2=N=100)，表示同学的总数。第一行有，表示同学的总数。第一行有n n个整数，用空格分隔，第个整数，用空格分隔，第i i个整数个整数Ti(130=Ti=230)Ti(130=Ti=230)是第是第i i位同学的身高位同学的身高(厘米厘米)。Output Output 包括一行，这一行只包含一个整数，就是最少需要几位同学出列。包括一行，这一行只包含一个整数，就是最少需要几位同学出列。Sample Input Sample Input 8186 186 150 2
49、00 160 130 197 220 8186 186 150 200 160 130 197 220 Sample Output Sample Output 4 4 Hint Hint 对于对于5050的数据，保证有的数据，保证有n=20n=20；对于全部的数据，保证有对于全部的数据，保证有n=100n=100。第58页，共89页，编辑于2022年，星期五解题思路解题思路解题思路解题思路：本题的方法思路和导弹拦截是一样的，但本题需要考虑两个满足题目要本题的方法思路和导弹拦截是一样的，但本题需要考虑两个满足题目要求的最长子序列。我们设求的最长子序列。我们设s s为身高序列，其中为身高序列，其中
50、sisi的为同学的为同学i i身高。身高。设设f1f1为由左向右身高递增的人数序列，其中为由左向右身高递增的人数序列，其中f1if1i为同学为同学1 1到同学到同学i i间（包括同间（包括同学学i i）身高满足递增顺序最多的人数。通过和导弹拦截相同的思路，我们可）身高满足递增顺序最多的人数。通过和导弹拦截相同的思路，我们可以得到如下的状态转移方程：以得到如下的状态转移方程：F1i:=maxf1j(F1i:=maxf1j(同学同学j j的身高的身高 同学同学i i的身高的身高)+1(1=j=i-1)+1(1=j=i-1同理：同理：同理：同理：设设f2f2为由右向左身高递减的人数序列，其中为由右向