山东省实验中学 宋凯强 Skywalker_Q,动态规划算法动态规划模型,讲解内容,神马是动态规划 重叠子问题 最优子结构性质 无后效性原则 总结 其他 动态规划的几种经典模型 资源型动态规划 区间型动态规划 状态压缩的动态规划 树形动态规划,什么是动态规划？,秦政大神说过：动态规划就是：,DP!,什么是动态规划History,动态规划(dynamic programming)运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。,什么是动态规划重叠子问题,【引例1】：爬楼梯 QZ大神要上楼梯，他一次可以上一层，也可以上两层。 【样例输入】： 4 【样例输出】： 5 【样例说明】： 1+1+1+1=4 1+1+2=4 1+2+1=4 2+1+1=4 2+2=4,算法一： Can U See The Code Below?,var n:integer; /n=90 function dp(i:integer):qword; begin if i=1 then exit(1);/begin dp:=1;exit;end if i=2 then exit(2); dp:=dp(i-1)+dp(i-2); end; begin readln(n); writeln(dp(n); end.,算法二：So I Need Notepad！,const maxn=90; var n:integer; f:array1.maxn of qword; function dp(i:integer):qword; begin if i=1 then exit(1); if i=2 then exit(2); if fi0 then exit(fi); dp:=dp(i-1)+dp(i-2); fi:=dp; end; Begin fillchar(f,sizeof(f),0); readln(n); writeln(dp(n); end.,分析,算法一： 当N=10的时候，这道题我们完全可以用暴力搜索来解决！ 我们可以搜索每个解决方案，是走一步还是走两步？ 时间复杂度O（ANS）,分析,算法二： 再进一步我们通过思考总结得到Fn=Fn-1+Fn-2的递推方程。可以通过递推或者记忆化搜索用O(n)的时间复杂度来解决此问题。,分析：,对比两个解决方法，为什么第二种比第一种时间效率更优呢？ 我们来看一下的一个图：,重叠子问题性质：假设N=6的时候,重叠子问题性质：假设N=6的时候,小问题？（有奖问答）,哪位同学能够回答一下这个问题？ 如果我用算法一实现程序，我计算F20的时候会多少次调用到F4的求解？,正确解答？,正确解答,设计算K的时候需要调用Gk次F4计算。则有： G4=1; G5=1; GK=GK-1+GK-2 (K5)； 所以有GK=FK-4次；,重叠子问题性质,观察上面两个图我们发现： 算法一之所以慢是因为它多次计算了同一个状态！如计算F6时我们计算了一次F4，计算F5时我们又计算了一次，重复的大量的无用的计算耗费了我们过多的时间！,怎么办？ 使用动态规划（广义上的动态规划也包括：递推和记忆化搜索）！ 如此看来动态规划之所以快：是因为它只计算了一次重叠的子问题！,什么是动态规划最优子结构,【引例2】：数字三角形 有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为7-3-8-7-5，和为30。,什么是动态规划最优子结构,输入样例： 5（有多少行，第i行有i个数） 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出样例： 30,分析,思路一：贪心 我们从最顶层出发，每次找一个下方数字最大的方向去走，在样例中就是7+8+1+7+5=28,分析：,思路二：动态规划 我们从最顶层出发，每次找一个下方最大路径最大的方向去走，在样例中就是7+3+8+7+5=30,分析,分析发现如果我们每次贪心的找一个最大的数，可能会导致我们的鼠目寸光，这一步的决策导致我们可能永远陷入一个局部较优解。而非全局最优解！而动态规划思路则是先把大的问题划分成了类似的小问题，通过小问题的最优解的合并得到大问题的最优解。,分析,可以认为： 贪心是：局部最优则全局最优的短见； 动态规划是：全局最优则局部最优的长远眼光；,具体解决方法,Fi,j表示从（i，j)走到底层的最大和。显然有：Fi,j=Max(Fi+1,j,Fi+1,j+1)+Ai,j; 然后我们从下往上搞一遍或者记忆化搜索就好了！ 具体实现给出2种。,算法一：记忆化搜索,Procedure dfs(i,j:integer); begin if i=n then begin fi,j:=ai,j; exit; end; if fi,j0 then exit; dfs(i+1,j); dfs(i+1,j+1); fi,j:=max(fi+1,j,fi+1,j+1)+ai,j; end;,算法二：递推,procedure work； begin 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); end;,小问题？（有奖问答）,如果我特殊的加入如若干条件，使得该路径必须经过某些点，此题该如何求解？,正确解答？,什么是动态规划无后效性原则,【引例3】：Mod M最大问题 给你N个数你可以选或者不选，使得所有选出的数的总和除M取余数最大。,什么是动态规划无后效性原则,【样例输入】： 3 4 （N=3，M=4） 1 1 2 【样例输出】 3,分析,我们设Fi表示前i个数选与不选所得到的最大Mod M的值。 Fi=Max(Fi-1+Xi) Mod M,Fi-1) 不过这显然是不对的！因为我们观察样例如果照此F4=2，而Mod 4最大显然该是3。,分析,观察我们当前的一步决策会影响到下一步的选择，这显然产生了后效性。即我们没有最优的决策！如此状态下我们就不能使用常见的动态规划了。 而事实上我们可以加一维Mod M的值是否出现，然后写一个递推解决此问题。但它不是严格意义上的DP。,什么是动态规划总结,动态规划是解决一类满足：重叠子问题、最优子结构和无后效性原则的问题的一种算法（思路）。 一般我们用Fi表示某个状态（i可能是多个值）的最优值，而一般动态规划方程会写作：Fi=opt(Fk+Wk,i)（k能转移到i）的形式。其中Opt表示对于一个状态的决策。,什么是动态规划总结,几个概念： 阶段：状态可以从前一个阶段转移到下一个阶段。 状态：对于一类子问题的某种描述 状态转移：从一个状态转移到另一个状态 决策：对于某个状态的每个转移都是一个决策。 值得注意的是一个DP可能没有阶段划分，但不能没有状态、状态转移和决策。,什么是动态规划总结,小问题？（有奖问答）,请你为上面的那个图加一条边使得它具有后效性！,正确解答？,动态规划相关的一些东西,拓扑网络：动态规划大多数是在拓扑网络上进行的，并以此保证其无后效性原则。 动态规划实质就是：在状态空间中寻找一条从初始状态到目标状态的最短路（最长路）,动态规划相关的一些东西,一系列“有后效性”的动态规划的解决办法： SPFA（详见JBY的论文、NOIP2009Trade）、扫荡法（HSW大神发明的名词）,动态规划相关的一些东西,动态规划优化的必要知识： 动态规划的时间复杂度=状态总量*状态转移时间 总之动态规划是个很常用很好用很好出题很好做题的算法！ 下面我们来讲讲动态规划的一些经典模型！希望大家能触类旁通！,动态规划的经典模型,休息一下！马上回来！,动态规划的经典模型资源型DP,【例题1】：0/1背包问题 给定一个容量为M的背包，有N件物品体积和权重分别为Vi和Wi（都为整数）。现在想要把这N件物品有选择性的放进背包中，求如何使得背包中的物品权重和最大？只需要求得最大的权重和是多少即可。,分析,设Fi,j表示前i件物品使用了容量为j的背包所得到的最大权重和。 其中Fi,j=Max(Fi-1,j,Fi-1,j-Vi+Wi)，分别表示两种决策拿或者不拿。 初始状态：F0,0=0; 目标状态：Fn,m,总结,类似的题目还有许多，他们往往是需要花费一定的代价来获取另一种收益，同时要求收益最大化，或者相反的要求代价最小化。这类问题我们一般以物品作为阶段，以资源作为状态，通过类似上题的方程解决问题。,分析,推荐： NOIP2010 乌龟棋 背包九讲,动态规划的经典模型区间型DP,【例题2】：石子合并 操场上排着一列石子共N堆，每堆重Wi。你要把它们合并成一堆，只允许合并相邻的两堆，求最小的合并代价。合并两堆的代价是两堆的重量和。,分析,我们考虑最终的一堆，它必定有之前的2堆合并而来，由于只能合并相邻的两堆，所以这两堆一定是两个连续的区间1.i和i+1.N。,分析,所以我们设Fi,j表示将区间i，j合并成一个堆的最小代价，其中显然有Fi,j=Min(Fi,k+Fk+1,j)+sumi,j; ( i=kj) 初始状态Fi,i=0; 目标状态F1,n; 注意：本题阶段是区间长度，所以最外层当枚举区间长度,总结,这一类问题是一类区间合并类型的动态规划问题，一般都需要以区间的长度为阶段，内层要枚举区间的开始端点和划分位置，将大区间划分成小区间，合并小区间的解求解大区间的解。,总结：,推荐： 火星人的项链 加分二叉树,动态规划经典模型状态压缩DP,【例3】：哈密顿路个数问题 给定一个节点数为N，边数为M的地图，求经过每个点一次的路径的个数。其中N=20，M=N*(N-1)/2。,分析,此题爆搜的时间复杂度是O(N！)显然在N=20的数据范围内会严重超时。怎么办？利用状态压缩的动态规划。状态设计：令Fi,j表示经过了i集合的点，最终末尾在j点上的方案总数,分析,Fi,j=(Fi-j,k*wk,j)； 其中wk,j表示k到j的边的个数。 初始状态：Fi,i=1; 目标状态：FAll,i,分析,对于一个集合如何表示我们用一串0,1表示该元素是否在集合中出现。即记录一个2进制数即可，当然这里的i要转化成10进制出现在数组下标中。 时间复杂度O(2N*N2),总结,这一类问题总是需要表示一个集合中的元素。我们可以利用2进制的方式将状态进行压缩存储。因此被称为状态压缩的动态规划。经常会有一个数据范围非常小，这就是提示我们可以记录所有的该状态的信息并进行状压DP。,总结,推荐： 2*1拼图问题 CDQ的基于连通性的状态压缩动态规划（可以忽略这条）,动态规划的经典模型树形DP,【例题4】：树的最长链 给定N个节点的一棵无根树，求树的最长链。每条边的权值为任意实数。,分析,此题有多种做法，其中一种就是树形DP。首先我们指定一个根，当成一棵有根树来做此题。对于每棵子树我们记录如下两个信息Fx,0表示一条从子树中任意结点连接到根节点的路径最大和，Fx,1表示次大和,Fx,2表示以x为根的子树的最长链。,分析,Fx,0=Max(Fy,0+Wx,y,0)； Fx,1=Max(Second(Fy,0+wx,y),0); Fx,2=Max(Fy,2,Fx,0+Fx,1); 目标状态Froot,2,总结,树形DP这