动态规划算法

动态规划算法第1页，共169页，2023年，2月20日，星期日前言：各类信息学竞赛的重要考察内容。不同于其他算法和数据结构，没有固定的结构框架。对选手能力有较高要求（函数思想）。初学者不易掌握其思想，需要做大量的题。典型的问题。会做不代表真正掌握。主要是分析问题的方法和思路；其次是代码。2第2页，共169页，2023年，2月20日，星期日在三个竞赛中的首次出现：数字三角形 【IOI1994】石子合并 【NOI1995】导弹拦截 【NOIP1999】3第3页，共169页，2023年，2月20日，星期日目录：两个引例动态规划的基本概念动态规划的常见模型及例题4第4页，共169页，2023年，2月20日，星期日引例1：数字三角形【IOI1994】有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。下图数据的路应为: 7->3->8->7->5，和为30。输入：第一行：n(1<=n<=100),数字三角形共有n行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且<=100.输出：一个正整数，路径上数字之和的最大值。7388102744452655第5页，共169页，2023年，2月20日，星期日6输入样例：5738810274445265输出样例：30第6页，共169页，2023年，2月20日，星期日样例：i,ji+1,ji+1,j+17第7页，共169页，2023年，2月20日，星期日8第8页，共169页，2023年，2月20日，星期日路径数字最大和：7+3+8+7+5=309第9页，共169页，2023年，2月20日，星期日深度优先搜索算法：Proceduredfs(i,j,sum)//从(1,1)走到（i，j）位置所求和sumBeginifi=nthen//走到最后一行ans=max(ans,sum);exit;dfs(向左下方走)；dfs(向右下方走)；End;10第10页，共169页，2023年，2月20日，星期日代码实现：//二维数组a[i,j]存储数字三角形。proceduredfs(i,j,sum:integer);beginifi=nthenbeginifsum>ansthenans:=sum;exit;end;dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;初始：dfs(1,1,a[1,1]);结果：ansi,ji+1,ji+1,j+111i,ji+1,ji+1,j+1第11页，共169页，2023年，2月20日，星期日n<=100超时！12第12页，共169页，2023年，2月20日，星期日N=109263531825146385932588470293882535020119968561497607471333951962796078786124494136303223163231325676748313第13页，共169页，2023年，2月20日，星期日每个位置被计算过的次数：1111211331146411510105116152015611721353521711828567056288119368412612684369114第14页，共169页，2023年，2月20日，星期日代码实现：//二维数组a[i,j]存储数字三角形。proceduredfs(i,j,sum:integer);begin

inc(count[i,j]);//全局计数器ifi=nthenbeginifsum>ansthenans:=sum;exit;end;dfs(i+1,j,sum+a[i+1,j]);dfs(i+1,j+1,sum+a[i+1,j+1]);end;i,ji+1,ji+1,j+115第15页，共169页，2023年，2月20日，星期日搜索速度慢的原因是做了很多重复的计算实际上：从（i,j）走到最后一行；路线上和的最大值不变。92635318251463859325884702938825

35020119968561497607471333951962796078786124494136303223163231325676748316第16页，共169页，2023年，2月20日，星期日所以：第一次求完(i,j)到达最后一行的最大值后，用f[i,j]记录下来。以后再遇到时不需要再搜索求解，可以直接使用f[i,j]，从而大大的节省时间。记忆化搜索17第17页，共169页，2023年，2月20日，星期日记忆化搜索算法：//a[i,j]记录数字三角形//f[i,j]:从(i,j)走到最后一行的和的最大值；初始-1Proceduredfs(i,j:integer);//求(i,j)到最后一行的最大和

beginifi=nthenbeginf[i,j]:=a[i,j];exit; end;

iff[i,j]>=0thenexit;//已经求过了，无需再求dfs(i+1,j);dfs(i+1,j+1);f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];end;dfs(1,1);ans=f[1,1];18i,ji+1,ji+1,j+1第18页，共169页，2023年，2月20日，星期日每个点的计算次数：n=101111111111111111111111111111111111111111111110000000000N<=100;问题解决了19第19页，共169页，2023年，2月20日，星期日思考记忆化搜索的求解过程：i,ji+1,ji+1,j+1……20f[i,j]:

(i,j)到最后一行的和的最大值；Ans=f[1,1]第20页，共169页，2023年，2月20日，星期日换一种方法实现：//f[i,j]

：从(i,j)走到最后一行的和的最大值；fori:=1tondof[n,i]:=a[n,i]; //最后一行fori:=n-1downto1do //从第n-1行向上求forj:=1toidof[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];writeln(f[1,1]);递推法：倒推21第21页，共169页，2023年，2月20日，星期日i,ji-1,j-1i,j顺推：22f[i,j]

：从(1,1)走到(i,j)的和的最大值；Ans=max{f[n,i]}i:1..n第22页，共169页，2023年，2月20日，星期日顺推：//f[i,j]

：从(1,1)走到(i,j)的和的最大值；f[1,1]:=a[1,1];fori:=2tondoforj:=1toidof[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];ans:=f[n,1]; //找最大的f[n,i]fori:=2tondoiff[n,i]>ansthenans:=f[n,i];writeln(ans);23边界情况?第23页，共169页，2023年，2月20日，星期日24边界问题的解决：方法一：varf:array[0..100,0..100]oflongint;把第0行及第0列元素初始化为0。方法二：把f[i,1]和f[i,i]作为特殊情况单独处理，即：fori:=2tondobeginf[i,1]=f[i-1,1]+a[i,1];f[i,i]=f[i-1,i-1]+a[i,i];forj:=2toi-1dof[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];end;第24页，共169页，2023年，2月20日，星期日回顾本题：重复的子问题。用表记录子问题的解，以后可以直接使用。有明显的阶段性。求解方法：记忆化搜索；递推。25第25页，共169页，2023年，2月20日，星期日引例2：公共汽车【问题描述】

一个城市的道路，南北向的路有n条，并由西向东从1标记到n,东西向的路有m条，并从南向北从1标记到m,每一个交叉点代表一个路口，有的路口有正在等车的乘客。一辆公共汽车将从(1,1)点驶到（n,m）点，车只能向东或者向北开.问：司机怎么走能接到最多的乘客。nm(n,m)26北南西东第26页，共169页，2023年，2月20日，星期日【输入】第一行是n,m和k,其中k是有乘客的路口的个数。以下k行是有乘客的路口的坐标和乘客的数量。已知每个路口的乘客数量不超过1000000。n,m<=1000.【输出】接到的最多的乘客数。bus.inbus.out87114346242325612521552113117717428621127第27页，共169页，2023年，2月20日，星期日a[i,j]:(i,j)位置的人数;f[i,j]:从(1,1)走到(i,j)能接的最多人数。f[i,j]:=max{f[i-1,j],f[i,j-1]}+a[i,j]28第28页，共169页，2023年，2月20日，星期日递推实现：varf[0..1000,0..1000]oflongint;fillchar(f,sizeof(f),0);fori:=1tondo //按列forj:=1tomdo //按行f[i,j]:=max(f[i-1,j],f[i,j-1])+a[i,j];writeln(f[n,m]);29第29页，共169页，2023年，2月20日，星期日二、动态规划的基本概念动态规划（DynamicProgramming简称DP）。解决“多阶段决策问题”的一种高效算法。通过合理组合子问题的解从而解决整个问题解的一种算法。其中的子问题并不是独立的，这些子问题又包含有公共的子子问题。……动态规划算法就是对每个子问题只求一次，并将其结果保存在一张表中(数组)，以后再用到时直接从表中拿过来使用，避免重复计算相同的子问题。“不做无用功”的求解模式，大大提高了程序的效率。动态规划算法常用于解决统计类问题（统计方案总数）和最优值问题（最大值或最小值），尤其普遍用于最优化问题。30第30页，共169页，2023年，2月20日，星期日定义：f[i,j]

：从(i,j)走到最后一行的和的最大值；目标：f[1,1]倒推求解过程f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];31第31页，共169页，2023年，2月20日，星期日

1、阶段：

把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。阶段的划分一般根据时间和空间来划分的。

2、状态：

某一阶段的出发位置成为状态，通常一个阶段有多个状态。

状态通常可以用一个或一组数来描述，称为状态变量。

3、决策：

一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。描述决策的变量称决策变量

4、策略和最优策略

所有阶段的决策有序组合构成一个策略。

最优效果的策略叫最优策略。32动态规划的术语：第32页，共169页，2023年，2月20日，星期日33例：最短路径问题

现在，我们想从城市A到达城市E。

怎样走才能使得路径最短，最短路径的长度是多少？AB1B2C1C2C3C4D1D2D3E531638438556343第33页，共169页，2023年，2月20日，星期日34阶段1阶段2阶段3阶段4阶段5第1部分：A第2部分：B1，B2第3部分：C1，C2，C3，C4第4部分：D1，D2，D3第5部分：EAB1B2C1C2C3C4D1D2D3E531638438556343第34页，共169页，2023年，2月20日，星期日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)=min{d(C1,D1)+f(D1),d(C1,D2)+f(D2)}=min{8,10}=8f(C2)=d(C2,D1)+f(D1)=8f(C3)=d(C3,D3)+f(D3)=11f(C4)=d(C4,D3)+f(D3)=6第2阶段:f(B1)=min{d(B1,C1)+f(C1),d(B1,C2)+f(C2),d(B1,C3)+f(C3)}=min{1+8,6+8,3+11}=9f(B2)=min{d(B2,C2)+f(c2),d(B2,C4)+f(C4)}=min{8+8,4+6}=10第1阶段:f(A)=min{d(A,B1)+f(B1),d(A,B2)+f(B2)}=min{5+9,3+10}=13最短路径：A->B2->C4->D3->E最短距离：13第35页，共169页，2023年，2月20日，星期日36fk[x]=min{fk+1[yi]+d

[x,yi]}状态转移方程：由已求得的状态来求未知状态的递推关系式称为状态转移方程。Xy1y2yiEF[x]:x到终点的最短距离。目标是f1[A]倒推：第36页，共169页，2023年，2月20日，星期日37fk[x]=min{fk-1[yi]+d

[yi,x]}F[x]:起点到x最短距离。目标是f5[E]顺推：Xy1y2yiA第37页，共169页，2023年，2月20日，星期日38一般形式：

U：状态；

X：策略顺推：f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}

L[Uk-1,Xk-1]：状态Uk-1通过策略Xk-1到达状态Uk

的费用初始f[U1]；结果：f(Un)第38页，共169页，2023年，2月20日，星期日39一般形式：

U：状态；

X：策略倒推：

f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}

L[Uk,Xk]：状态Uk通过策略Xk到达状态Uk+1

的费用初始f[Un]；结果：f(U1)第39页，共169页，2023年，2月20日，星期日40动态规划问题的特征:1、最优子结构

如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。

2、重叠子问题

在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题……。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。第40页，共169页，2023年，2月20日，星期日3、无后效性原则41已经求得的状态，不受未求状态的影响。第41页，共169页，2023年，2月20日，星期日42最优子结构、重叠子问题、无后效性阶段1阶段2阶段3阶段4阶段5AB1B2C1C2C3C4D1D2D3E531638438556343第42页，共169页，2023年，2月20日，星期日43第43页，共169页，2023年，2月20日，星期日44拓扑图（有向无环图）无后效性第44页，共169页，2023年，2月20日，星期日45非拓扑图（可能有环）有后效性abc？bca？

abc51111第45页，共169页，2023年，2月20日，星期日46动态规划的条件：

无后效性、最优子问题无后效性、最优子问题是否能满足与状态的表示、阶段的划分、状态的转移有关第46页，共169页，2023年，2月20日，星期日47

1、找出最优解的性质，并刻画其结构特征；

2、递归地定义最优值（写出动态规划方程）；

3、以自底向上的方式计算出最优值；

记忆化搜索（树型）、递推

4、根据计算最优值时得到的信息，构造一个最优解。

设计动态规划法的步骤：第47页，共169页，2023年，2月20日，星期日48状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）.定量处理的过程也就是决策实施的过程.动态规划的关键：第48页，共169页，2023年，2月20日，星期日49f[Un]=初始值；fork←n-1downto1do//枚举阶段

forU取遍所有状态do//枚举状态forX取遍所有决策do//枚举决策f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}；

L[Uk,Xk]：状态Uk通过策略Xk到达状态Uk+1的费用输出：f[U1]:目标动态规划的一般倒推格式为：第49页，共169页，2023年，2月20日，星期日50//f[i,j]

：从(i,j)走到最后一行的和的最大值；fori:=1tondof[n,i]:=a[n,i]; //初始fori:=n-1downto1do //阶段forj:=1toido //状态f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j]; //决策writeln(f[1,1]);第50页，共169页，2023年，2月20日，星期日51f[U1]=初始值；fork←2tondo //枚举每一个阶段

forU取遍所有状态doforX取遍所有决策dof[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}；

L[Uk-1,Xk-1]：状态Uk-1通过策略Xk-1到达状态Uk

的费用输出：f[Un]:目标动态规划的一般顺推格式为：第51页，共169页，2023年，2月20日，星期日顺推：//f[i,j]

：从(1,1)走到(i,j)的和的最大值；f[1,1]:=a[1,1]; //初始化fori:=2tondo //阶段forj:=1toido //状态f[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j]; //决策//找最大的f[n,i]ans:=f[n,1];fori:=2tondoiff[n,i]>ansthenans:=f[n,i];writeln(ans);52第52页，共169页，2023年，2月20日，星期日53贪心算法：采用“自顶向下”的方式使用最优子结构：先做决策，选在当时看起来是最优的选择（只顾眼前利益），然后再求解决策后的那个子问题。“先决策，再求解子问题”DP:“先求得子问题的解，然后决策”。73881027

4445265动态规划与贪心算法的不同：第53页，共169页，2023年，2月20日，星期日通过做大量的题目，慢慢理解和体会DP其中的……54第54页，共169页，2023年，2月20日，星期日三、DP常见模型55线性型坐标型区间型背包型树型动态规划有多种多样的题目，通常按照状态可分为以下几类：第55页，共169页，2023年，2月20日，星期日（一）、线性模型56线性动态规划状态是一维的（f[i]）。正推：第i个元素的最优值只与前i-1个元素的最优值有关。倒推：第i个元素的最优值只第i+1个元素之后的最优值有关。经典的线性DP题目有最长上升子序列、最大连续子序列和、最长公共子序列等。第56页，共169页，2023年，2月20日，星期日1.最长上升子序列模型57例1导弹拦截【NOIP1999】【问题描述】某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统，但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，不能拦截所有的导弹，输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），请聪明的你帮忙计算这套系统最多能拦截多少导弹。【输入】第一行：n（<=1000），敌国导弹的数量。第二行：n个整数，用空格分隔，依次是敌国导弹的高度(<30000)。【输出】最多拦截敌国导弹的数量。【数据规模】对于100%的数据：n<=1000。第57页，共169页，2023年，2月20日，星期日58【样例输入输出】bumb.inbumb.out8271910123

4

题意简述：

给定n个元素的数列，求最长的上升子序列长度。即：在原序列中，最多能选多少个数，在原有顺序下递增。第58页，共169页，2023年，2月20日，星期日最长上升子序列长度（LIS）：59最长上升子序列显然是以某一个a[i]作为第一元素的一个最长上升子序列。如果求出以原序列中每一个元素a[i]作为第一个元素开头的最长上升子序列长度f[i].那么:ans=max{f[i]}；i=1..n问题是怎么求f[i]?8271910143第59页，共169页，2023年，2月20日，星期日倒推法：60a[i]:数列中的第i个数。f[i]:以a[i]为开始(a[i]是被选中的第一个元素)的最长递增子序列的序列长度。转移方程：f[i]=max{f[j]}+1条件：i<j<=n并且a[i]<a[j]边界：f[n]=1;目标：max{f[i]};1<=i<=n8271910143第60页，共169页，2023年，2月20日，星期日倒推参考程序：61f[n]:=1;fori:=n-1downto1dobeginforj:=i+1tondoif(a[j]>a[i])and(f[j]>f[i])thenf[i]:=f[j]; //找最大的f[j]inc(f[i]); //包含a[i]end;ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];writeln(ans);第61页，共169页，2023年，2月20日，星期日顺推：62a[i]:数列中的第i个数。f[i]:以a[i]为结尾(a[i]是被选中的最后一个元素)的最长递增子序列的序列长度。f[i]=max{f[j]}+1

条件：1<=j<i并且a[j]<a[i]边界：f[1]=1;目标：max{f[i]};1<=i<=n8271910143第62页，共169页，2023年，2月20日，星期日顺推参考程序：63f[1]:=1;fori:=2tondobeginforj:=1toi-1doif(a[j]<a[i])and(f[j]>f[i])thenf[i]:=f[j]; //找最大的f[j]inc(f[i]); //包含a[i]end;ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];writeln(ans);第63页，共169页，2023年，2月20日，星期日最长上升子序列长度（LIS）：64

倒推：f[i]:以a[i]为开始元素的最长递增子序列的序列长度。转移方程：f[i]=max{f[j]}+1条件：i<j<=n并且a[i]<a[j]边界：f[n]=1;目标：max{f[i]};1<=i<=n第64页，共169页，2023年，2月20日，星期日顺推：65f[i]:以a[i]为结尾的最长递增子序列的序列长度。f[i]=max{f[j]}+1

条件：1<=j<i并且a[j]<a[i]边界：f[1]=1;目标：max{f[i]};1<=i<=n时间复杂度：O(n2)第65页，共169页，2023年，2月20日，星期日知识扩展：66最长上升子序列长度； <最长不下降子序列长度； <=最长下降子序列长度；

>最长不上升子序列长度。 >=第66页，共169页，2023年，2月20日，星期日例2：合唱队形[NOIP2004]67【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，……，K，他们的身高分别为T1,T2,……,Tk,则他们的身高满足T1<T2<……Ti，Ti>Ti+1>……>Tk(1<=i<=K)。你的任务是：已知有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。第67页，共169页，2023年，2月20日，星期日68【样例输入输出】chorus.inchorus.out8186186150200160130197220

4【输入】第一行是一个整数N(2<=N<=1000),表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高（厘米）。【输出】一个整数，表示最少需要几位同学出列。【数据规模】对与全部的数据，保证有n<=1000。第68页，共169页，2023年，2月20日，星期日问题分析:69计算最少需要几位同学出列，可转化为计算最多能留下多少同学。将所有合唱队形同学排为一列，在二维坐标系中根据身高描点连线，图样就像一座山峰。队列左边的身高依次上升，右边依次下降，中间有一个最高点，而这个最高点的左侧是上升子序列，右侧是下降子序列。人数最多是最优合唱队形。第69页，共169页，2023年，2月20日，星期日算法描述：70对整个身高序列a[i]做：一次最长上升子序列(f[i])：正推求；一次最长下降子序列(g[i])：倒推求；之后枚举最高点a[i]:ans=max(f[i]+g[i]-1)是保留最大值。最少出队列人数:n-ans.第70页，共169页，2023年，2月20日，星期日参考代码：71a[i]:身高。f[i]:以a[i]为最后一个人最长上升子序列长度

f[1]:=1;fori:=2tondobeginforj:=1toi-1doif(a[j]<a[i])and(f[j]>f[i])thenf[i]:=f[j];inc(f[i]);end;第71页，共169页，2023年，2月20日，星期日72//g[i]:以a[i]开头的最长下降子序列长度g[n]:=1;fori:=n-1downto1dobeginforj:=i+1tondoif(a[j]<a[i])and(g[j]>g[i])theng[i]:=g[j];inc(g[i]);end;

第72页，共169页，2023年，2月20日，星期日枚举以第i位同学为最高的队形：73ans:=0;//保留的最多人数。fori:=1tondoiff[i]+g[i]-1>ansthenans:=f[i]+g[i]-1;writeln(n-ans);//最少出队人数第73页，共169页，2023年，2月20日，星期日例3：上帝选人74【问题描述】

世界上的人都有智商IQ和情商EQ。我们用两个数字来表示人的智商和情商，数字大就代表其相应智商或情商高。现在你面前有N个人，这N个人的智商和情商均已知，请你选择出尽量多的人，要求选出的人中不存在任意两人i和j，i的智商大于j的智商但i的情商小于j的情商。【输入】第一行一个正整数N，表示人的数量。第二行至第N+1行，每行两个正整数，分别表示每个人的智商和情商。【输出】仅一行，为最多选出的人的个数。第74页，共169页，2023年，2月20日，星期日75【数据规模和约定】N<=1000；【输入输出样例】select.inselect.out310010012090110802第75页，共169页，2023年，2月20日，星期日问题分析：76原题中的要求“不存在任意两人i和j，i的智商大于j的智商，但i的情商小于j的情商。”将其转化成：就是要求不存在i,j满足：

如果（iq[i]>iq[j]），但(eq[i]<eq[j])。即选出的人i和j要满足：(IQ[i]>=IQ[j])and(EQ[i]>=EQ[j])或者(IQ[i]<=IQ[j])and(EQ[i]<=EQ[j])第76页，共169页，2023年，2月20日，星期日再形象一点：7780901002507085100120第77页，共169页，2023年，2月20日，星期日78对于所有选出的人：当IQ有序时，EQ必定是有序的（连线不相交）。同序80901002507085100120第78页，共169页，2023年，2月20日，星期日79IQEQ10269211219815IQEQ81592110261219第79页，共169页，2023年，2月20日，星期日80IQEQ115106106105IQEQ105106106115第80页，共169页，2023年，2月20日，星期日设计算法：811.将所有人IQ（或者EQ）从小到大排序。2.求EQ（或者IQ）的最长非递减子序列长度.第81页，共169页，2023年，2月20日，星期日例4：递增子序列最大和82【问题描述】给定长度为n的正整数序列a1,a2,…,an。求一个递增的子序列，和最大。【输入】第一行，n，表示给定序列的个数。第二行，n个用空格隔开的正整数。【输出】递增子序列的最大和。【数据范围限制】n<=1000,0<ai<=109。第82页，共169页，2023年，2月20日，星期日83【输入输出样例】Sum.inSum.out6241205626递增的子序列最大和：2+4+20=26。不是最长递增子序列LIS而是简单变形！第83页，共169页，2023年，2月20日，星期日算法描述：84定义f[i]表示以a[i]为最后一个数的递增子序列的最大和。2412056f[i]:=max(f[j])+a[i]

（1<=j<i且a[j]<a[i]）Ans=max{f[i]}i=1..n时间：O(n*n)第84页，共169页，2023年，2月20日，星期日参考代码：85f[1]:=a[1];ans:=0;fori:=2tondobeginforj:=1toi-1doif(a[j]<a[i])thenf[i]:=max(f[i],f[j]);f[i]:=f[i]+a[i];end;fori:=1tondoiff[i]>ansthenans:=f[i];writeln(ans);第85页，共169页，2023年，2月20日，星期日2：最大连续子序列的和模型86求给定序列的最大连续子序列和。输入：第一行：n（n<100000）第二行：n个整数[-3000，3000]。输出：最大连续子序列的和。样例：输入：7-64-13

2-32输出：8例5第86页，共169页，2023年，2月20日，星期日87算法1：枚举任意连续区间[i,j]求和找最大值ans:=-300000000;fori:=1tondoforj:=itondobeginsum:=0;fork:=itojdosum:=sum+a[k];ifsum>ansthenans:=sum;end;writeln(ans);时间：O(n3)第87页，共169页，2023年，2月20日，星期日88算法2：算法1的稍加改进ans:=-300000000;fori:=1tondobeginsum:=0;forj:=itondobeginsum:=sum+a[j];ifsum>ansthenans:=sum;end;end;writeln(ans);时间：O(n2)第88页，共169页，2023年，2月20日，星期日891、以a[i]为结束点和以a[i-1]为结束点的最大连续子序列和有没有联系？有什么样的联系？2、如果事先已经求得了以a[i-1]为结束点的最大连续子序列和为x，那么怎样求以a[i]为结束点的最大连续子序列？-64-132-32继续分析：第89页，共169页，2023年，2月20日，星期日90a[i]:序列；f[i]：以a[i]为终点（连续区间的右边界）的子序列的最大和。时间：O(n)顺推法：f[i]=max{f[i-1]+a[i],a[i]}=max{f[i-1],0}+a[i]初始：f[1]=a[1]目标：max{f[i]}(1<=i<=n)第90页，共169页，2023年，2月20日，星期日91f[1]:=a[1];fori:=2tondof[i]:=max(f[i-1]+a[i],a[i]);ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];

第91页，共169页，2023年，2月20日，星期日92a[i]:序列；f[i]:从第i项开始(以第i项为第1项)的最大连续子序列的和。f[i]=max{f[i+1]+a[i],a[i]}初始：f[n]=a[n]目标：max{f[i]}1<=i<=n-64-132-32倒推法：第92页，共169页，2023年，2月20日，星期日93f[n]:=a[n];fori:=n-1downto1dof[i]:=max(a[i]+f[i+1],a[i]);

ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];

第93页，共169页，2023年，2月20日，星期日94ans:=0;s:=0;fori:=1tondobegins:=s+a[i];ifs<0thens:=0;ifs>ansthenans:=s;end;writeln(ans);进一步分析上面的两种求解方法，新序列要么是在现有某序列的一端添加一个元素，要么是只包含该元素。第94页，共169页，2023年，2月20日，星期日例6：勤工俭学（下午上机题目）95f[0]:=0;d[0]:=0;fori:=1tondobeginiff[i-1]>0thenbeginf[i]:=f[i-1]+a[i];

d[i]:=d[i-1]+1;endelsebeginf[i]:=a[i];d[i]:=1;end;end;第95页，共169页，2023年，2月20日，星期日3.最长公共子序列问题LCS96最长公共子序列也称作最长公共子串(不要求一定连续)，英文缩写为LCS（LongestCommonSubsequence）。

其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。第96页，共169页，2023年，2月20日，星期日97给定两个序列

X={x1,x2,...,xm}

Y={y1,y2,...,yn}

求X和Y的一个最长公共子序列举例

X={a,b,c,b,d,a,b}

Y={b,d,c,a,b,a}

最长公共子序列为

LSC={b,c,b,a}

例7：第97页，共169页，2023年，2月20日，星期日98要求：X和Y以字符串输入，长度<=1000.输出：最长公共子串的长度如：输入：abcbdab

bdcaba输出4LCS=bcba

第98页，共169页，2023年，2月20日，星期日分析：99X=‘abcdefgh’Y=‘acneh’X=‘abcdefgh’Y=‘acnehk’X=‘abcdefgkh’Y=‘acnehk’X=‘abcdefgn’Y=‘acnem’第99页，共169页，2023年，2月20日，星期日分析：100X={x1,...,xi-1

，xi}

Y={y1,...,yj-1

，yj}f[i,j]:x的前i个和y的前j个字符的最大公共子序列长度。xi=yj时,f[i,j]=f[i-1,j-1]+1

xi<>yj时,f[i,j]=max{f[i,j-1],f[i-1,j]}第100页，共169页，2023年，2月20日，星期日参考代码：101fori:=1tondo //X的长度forj:=1tomdo //Y的长度beginf[i,j]:=0;ifx[i]=y[j]thenf[i,j]:=f[i-1,j-1]+1elsef[i,j]:=max(f[i-1,j],f[i,j-1]);end;第101页，共169页，2023年，2月20日，星期日（二）坐标类模型102比较简单的一类动态规划问题。常以二维空间坐标系为模板展开，因此状态转移方程也在坐标系中寻找，一般定义f[i,j]表示状态，此状态表示某个点的坐标。有关系的状态：f[i-1,j]，f[i,j-1]，f[i-1,j-1]按行或列的顺序求解问题。第102页，共169页，2023年，2月20日，星期日引例1：数字三角形【IOI1994】有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和的最大值。下图数据的路应为: 7->3->8->7->5，和为30。输入：第一行：n(1<=n<=100),数字三角形共有n行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且<=100.输出：一个正整数，路径上数字之和的最大值。738810274445265103第103页，共169页，2023年，2月20日，星期日引例2：公共汽车【问题描述】

一个城市的道路，南北向的路有n条，并由西向东从1标记到n,东西向的路有m条，并从南向北从1标记到m,每一个交叉点代表一个路口，有的路口有正在等车的乘客。一辆公共汽车将从(1,1)点驶到（n,m）点，车只能向东或者向北开.问：司机怎么走能接到最多的乘客。nm(n,m)104北南西东第104页，共169页，2023年，2月20日，星期日例8：最大正方形面积105【题目描述】给定一个R行C列的01矩阵，求一个最大的正方形全1子矩阵，并输出该最大正方形子矩阵的面积。【输入】第一行给出两个正整数R,C，表示矩阵有R行C列；接下来R行C列给出这个01矩阵，行内相邻两元素用一个空格隔开。R,C<=1000。第105页，共169页，2023年，2月20日，星期日106样例：matrix.inmatrix.out5800011101110111110111110110111110111011019

第106页，共169页，2023年，2月20日，星期日f[i,j]定义为以(i,j)为右下角顶点的最大正方形边长。最大正方形边长：ans=max{f[i,j]}1<=i<=R，1<=j<=C。最大面积：ans*ans107第107页，共169页，2023年，2月20日，星期日108Ifa[i,j]=0thenf[i,j]:=0;(i,j)(i-1,j-1)（i,j-1）(i-1,j)第108页，共169页，2023年，2月20日，星期日1111情况1：？(i,j)(i-1,j)(i-1,j-1)(i,j-1)f[i,j]=f[i-1,j]+1109第109页，共169页，2023年，2月20日，星期日1111？f[i,j]=f[i-1,j-1]+1情况2：110第110页，共169页，2023年，2月20日，星期日1111图3？f[i,j]=f[i,j-1]+1情况3：111第111页，共169页，2023年，2月20日，星期日当a[i,j]=1f[i,j]:=min{f[i,j-1],f[i-1,j],f[i-1,j-1]}+1;综上三种情况：112第112页，共169页，2023年，2月20日，星期日数字三角形2有一个数字三角形，从最顶层出发，每一步只能向左下或右下方向走。编程求从最顶层到最底层的一条路所经过位置上的数字之和mod100的最大值。输入：第一行：n(1<=n<=25),数字三角形共有n行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且<=100.输出：一个正整数，路径上数字之和mod100的最大值。19998111113第113页，共169页，2023年，2月20日，星期日114定义f[i,j]表示到达第i行第j列位置的最优值，则：f[i,j]=Max{ (f[i-1,j-1]+a[i,j])mod100,(f[i-1,j]+a[i,j])mod100}初始值：f[1,1]=a[1,1].max{f[n,i]}即为所求。错误作法！因为不具备最优子结构。第114页，共169页，2023年，2月20日，星期日115正确作法：定义f[i,j,k]表示到达第i行第j列位置能否得到k。(0<=k<=99).f[i,j,k]=f[i,j,k]or f[i-1,j-1,(k-a[i,j]+100)mod100]or f[i-1,j,(k-a[i,j]+100)mod100];初始值:f[1,1,a[1,1]]=true,其余均为false.第115页，共169页，2023年，2月20日，星期日（三）背包类模型116背包问题九讲第116页，共169页，2023年，2月20日，星期日有一个背包，最大载重量为m。有n种货物：重量为W[i](<1000)；

价值为V[i](<1000).今从ｎ种物品中选取若干件放入背包，使其重量之和不超过m，而所选货物的价值之和为最大。n<=100,m<1000.

求最大价值。例9：01背包基本模型117第117页，共169页，2023年，2月20日，星期日118输入样例1：

410

4357

1572025

输出样例1：

35输入样例2：

420

291015

291016

输出样例2：

19价值大的？单位价值大的？第118页，共169页，2023年，2月20日，星期日proceduredfs(i,left,value:longint);//在前i件物品中选了若干件放入到背包中，其价值为value，背包还能装的重量为left。beginifi=nthenifvalue>ansthenans:=value;

ifi=nthenexit; //防止越界

dfs(i+1,left,value); //不装i+1ifleft>=w[i+1]then //装i+1

dfs(i+1,left-w[i+1],value+v[i+1]);end;深度优先搜索算法:119第119页，共169页，2023年，2月20日，星期日n<=100时间:O(2n)dfs(0,m,0);120第120页，共169页，2023年，2月20日，星期日0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0--10物品0--4编号1234容量4357价值15720254件物品背包容量：10算法2：设f[i,j]:从1到i件物品中选取若干件放到容量为j的背包中，获得的最大价值。目标是：f[n,m]121第121页，共169页，2023年，2月20日，星期日用f[i,j]表示在第１到第i件物品中选择若干件到载重量为j的背包中所能获得的最大价值．f[i,j]=max{f[i-1,j],f[i-1,j-W[i]]+V[i]:(j>=w[i])}(1<=i<=n,1<=j<=m)目标：f[n,m];2)f[i-1,j-W[i]]+V[i]：

放第i件的价值。条件：j>=w[i]1)f[i-1,j]:不放第i件物品获得的价值。122第122页，共169页，2023年，2月20日，星期日主程序：fori:=1tondo

forj:=1tomdobeginf[i,j]:=f[i-1,j];

//不选择第i件物品

if(j>=w[i])and(f[i,j]<f[i-1,j-w[i]]+v[i]) //选择第i件物品

thenf[i,j]:=f[i-1,j-w[i]]+v[i];end;writeln(f[n,m]);end.123第123页，共169页，2023年，2月20日，星期日对于从1到N（1<=N<=39）的连续整数集合，划分成两个子集合，使得每个集合的数字之和相等。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：{3}and{1,2}这是唯一的一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）。如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分法的子集合各数字和是相等的:{1,6,7}and{2,3,4,5};{2,5,7}and{1,3,4,6};{3,4,7}and{1,2,5,6};{1,2,4,7}and{3,5,6}集合划分（subset）124第124页，共169页，2023年，2月20日，星期日125分析：如果用搜索算法求解，但效率较低，剪枝优化效果不够理想。1+2+…+n=n*(n+1)div2考虑n*(n+1)mod4的取值：nmod4=1或2时，方案数为0;nmod4=0或3时：第125页，共169页，2023年，2月20日，星期日令s=n*(n+1)div4问题转化为从1···n中取数，得到和为s的取数方法有多少种。为避免重复，不取数字1，f(i,j)表示从i···n中取数得到和为j的方案数，则：f(i,j)=f(i+1,j)+f(i+1,j-i)(2<=i<=n,0<=j<=s);f(n,0)=1;f(n,n)=1;其它值为0.f(2,s)即为题目的解。126第126页，共169页，2023年，2月20日，星期日fillchar(f,sizeof(f),0);f[n,0]:=1;f[n,n]:=1;fori:=n-1downto2doforj:=0ton*(n+1)div4dobeginf[i,j]:=f[i+1,j];ifj-i>=0thenf[i,j]:=f[i,j]+f[i+1,j-i];end;writeln(f[2,n*(n+1)div4]);127第127页，共169页，2023年，2月20日，星期日(四)区间型模型128区间型动态规划是线性动态规划的拓展，它将区间长度作为阶段，长区间的答案与短区间有关。在求解长区间答案前需先将短区间答案求出。区间型动态规划的典型应用有石子合并、乘积最大等。第128页，共169页，2023年，2月20日，星期日例10：石子合并129有N堆石子(N≤100)排成一排。现要将石子合并成一堆.规定每次只能选相邻的两堆合并成一堆新的石子,并将新的一堆的石子数,记为该次合并的得分.

选择一种合并石子的方案,使得做N-1次合并,得分的总和最少。

输入数据:

第一行为石子堆数N;

第二行为每堆石子数。输出数据:

合并石子后得到的最小得分。第129页，共169页，2023年，2月20日，星期日130如:41352最小得分：22贪心算法：

每次合并相邻两堆和最小的那两堆。第130页，共169页，2023年，2月20日，星期日反例：7447131贪心：8+15+22=45正确：11+11+22=44第131页，共169页，2023年，2月20日，星期日应该怎么合并呢？1323堆石子合并方案：11+（11+6）=289+（8+9）=26Ans=Min(28,26)=26836第132页，共169页，2023年，2月20日，星期日133N=4时，4堆一共合并了几次？最后一次合并成一堆前的那两堆什么样？8，18

或者13,13

或者18,8哪种情况是理想的情况：min（8+18,13+13,18+8）=26子问题变成3堆和2堆的情况。8558第133页，共169页，2023年，2月20日，星期日5堆石子：134(1,5)=min{(1,1)+(2,5);(1,2)+(3,5)；(1,3)+(4,5);(1,4)+(5,5)}+sum[1,5]第134页，共169页，2023年，2月20日，星期日n堆石子：n-1次合并135a1,a2,a3,…,an-1,anmin{(1..k)+(k+1..n)}+sum[1,n]

枚举：k=1..n-1重叠子问题和最优子结构性质(1,n)=min{(1,1)+(2,n);(1,2)+(3,n)；…(1,n-1)+(n,n)}+sum[1,n]第135页，共169页，2023年，2月20日，星期日动态规划算法：136定义f[i,j]表示从第i到第j堆间合并为一堆的最小代价。a[i],……,a[j]共有j-i+1堆石子sum[i,j]=a[i]+a[i+1]+…+a[j]状态转移方程：f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j]

枚举位置k：i<=k<=j-1初始：f[i,i]=0;ans=f[1,n]第136页，共169页，2023年，2月20日，星期日实现方法1：记忆化搜索137a[i]:记录第i堆石子数量。s[i]=a[1]+a[2]+…+a[i]。//前缀和sum[i,j]=s[j]-s[i-1].readln(n);s[0]:=0;fori:=1tondobeginread(a[i]);s[i]:=s[i-1]+a[i];end;第137页，共169页，2023年，2月20日，星期日搜索过程：138functiondfs(i,j:longint):longint; //合并i..jvark:longint;beginifi=jthenexit(0); //初始f[i,j]:=0;

iff[i,j]>0thenexit(f[i,j]); //已经求过f[i,j]:=maxlongint;/ /为求最小值准备fork:=itoj-1dof[i,j]:=min(f[i,j],

dfs(i,k)+dfs(k+1,j)+s[j]-s[i-1]);exit(f[i,j]); //dfs=f[i,j]返回函数值end;第138页，共169页，2023年，2月20日，星期日139072036476101025344801120340717060346524123456123456f[i,j]:第i到第j堆间合并为一堆的最小代价。f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j]第139页，共169页，2023年，2月20日，星期日140f[2,5]=min(f[2,2]+f[3,5];f[2,3]+f[4,5];f[2,4]+f[5,5])+sum[2,5]=min(20,10+7,25)+17=34第140页，共169页，2023年，2月20日，星期日递推法：合并第i堆到第j堆141fori:=1tondof[i,i]:=0;{初始化}forp:=1ton-1do//合并的堆数p:阶段fori:=1ton-pdo//枚举状态：beginj:=i+p;f[i,j]:=maxlongint;fork:=itoj-1do{枚举决策}

f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]);f[i,j]:=f[i,j]+s[j]-s[i-1];end;时间:O(n3)第141页，共169页，2023年，2月20日，星期日总结本题：1421、前缀和的应用。2、区间的dp的求解方法：

不能顺推也不能倒推。是以区间长度的大小划分阶段。按区间从小到大的顺序划分。第142页，共169页，2023年，2月20日，星期日扩展一下：NOI95143石子由一排改为围成一个环的形状？45944594459第143页，共169页，2023年，2月20日，星期日14445944594459第144页，共169页，2023年，2月20日，星期日环形石子合并算法：145环变成线性:长度:2n-1a[1],a[2]......a[n],a[n+1].....a[2n-1];