提高篇——动态规划专题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt精选版,*,提高篇,动态规划专题,1,ppt精选版,动态规划,递归 递推,一种精妙的算法思想。,特点：,没有固定的写法,具体问题具体分析,需要：,多练习、多思考、多总结,ppt精选版,什么是动态规划,最优化问题,1,复杂问题,2,分解子问题,3,记录每个解,4,Dynamic Programming,动态规划是一种用来解决一类,最优化问题,的算法思想。将一个,复杂的问题,分解成若干个,子问题,，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的,解记录下来,，这样可以提高计算效率，但,不,能说这种做法就,是,动态规划的,核心,。,ppt精选版,动态规划的递归写法,【,理解,】,如何记录子问题的解，来避免下次遇到相同的子问题时的重复计算。,斐波那契数列：,F,0,=1,F,1,=1,F,n,=F,n-1,+F,n-2,(n=2),int F(int n),if(n=0|n=1)return 1;,else return F(n-1)+F(n-2);,一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处又称作,记忆化搜索,。,缺点：重复计算。当,n=5,时，,F(5)=F(4)+F(3),接下来计算,F(4)=F(3)+F(2),这样,F(3),就被计算了两次。如果,n,很大，时间复杂度会高达,O(2,n,),。,ppt精选版,避免重复计算,开一个一维数组,dp,，用于保存已经计算过的结果，其中,dpn,记录,F(n),的结果，并用,dpn=-1,表示,F(n),当前还没有被计算过。,int dpmaxn;,int F(int n),if(n=0|n=1)return 1;/,递归边界,if(dpn!=-1)return dpn;/,已经计算过，直接返回结果，不再重复计算,else,dpn=F(n-1)+F(n-2);/,计算,F(n),，并保存至,dpn,return dpn;/,返回,F(n),的结果,记忆化搜索,时间复杂度,O(2,n,),降到了,O(n),ppt精选版,时间复杂度对比图,斐波那契数列递归图,O(2,n,),斐波那契数列记忆化搜索,O(n),ppt精选版,重叠子问题,（,Overlapping Subproblems,）,如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。,一个问题必须拥有,重叠子问题,，才能使用,动态规划,去解决。,ppt精选版,动态规划的递推写法,【,数塔问题,】,将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字,第,n,层有,n,个数字。现在要从第一层走到第,n,层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大是多少？,5,8,3,7,12,4,9,10,5,16,11,3,6,9,4,ppt精选版,动态规划的递推写法,如果开一个二维数组,f,，其中,fij,存放第,i,层的第,j,个数字，那么就有,f11=5,f21=8,f22=3,f31=12,f54=9,f55=4,。,如果尝试穷举所有路径，然后记录路径上的数字和的最大值，那么由于每层中的每个数字都会有两条分支路径，因此时间复杂度为,O(2,n,),，这在,n,很大的情况下是不可以接受的。那么，产生这么大复杂度的,原因,是什么？,从,5,出发，按,5,87,的路线来到,7,，并枚举,从,7,出发的到达最底层的所有路径,。但是，之后当按,5,37,的路线再次来到,7,时，又会去枚举,从,7,出发的到达最底层的所有路径,，这就导致了,从,7,出发的到达最底层的所有路径,都被,反复,地访问。其实，可以把路径上能产生的最大和记录下来，这样就可以避免重复计算。,所以令,dpij,表示从第,i,行第,j,个数字出发的到达最底层的所有路径中能得到的最大和，例如,dp32,就是,7,的最大和。那么,dp11,就是最终答案，现在想办法,求出,它。,注意一个细节：如果要求出“从位置（,1,1,）到达最底层的最大和”,dp11,，那么一定要先求出它的两个子问题“从位置（,2,1,）到达最底层的最大和,dp21,”和“从位置（,2,2,）到达最底层的最大和,dp22,”，即进行了一次,决策,：走数字,5,的左下还是右下。于是,dp11,就是,dp21,和,dp22,的较大值加上,5,。公式：,dp11=max(dp21,dp22)+f11,ppt精选版,动态规划的递推写法,归纳：如果要求出,dpij,，那么一定要求出它的两个子问题“从位置,(i+1,j),到达最底层的最大和,dpi+1j,”和“从位置,(i+1,j+1),到达最底层的最大和,dpi+1j+1,”，即进行了一次,决策,：走位置,(i,j),的左下还是右下。公式：,dpij=max(dpi+1j,dpi+1j+1)+fij,把,dpij,称为问题的,状态,，公式称为,状态转移方程,，它把状态,dpij,转移为,dpi+1j,和,dpi+1j+1,。可以发现，状态,dpij,只与第,i+1,层的状态有关，而与其他层的状态无关。那么如果总是将层号增大，什么时候会到头呢？其实，数塔的最后一层的,dp,值总是等于元素本身，即,dpnj=fnj(1=jn;,for(int i=1;i=n;i+),for(int j=1;jfij;/,输入数塔,for(int j=1;j=1;i-),for(int j=1;j=i;j+),dpij=max(dpi+1j,dpi+1j+1)+fij;/,动态转移方程,coutdp11endl;,return 0;,ppt精选版,动态规划的递推写法,输入数据,5,5,8 3,12 7 16,4 10 11 6,9 5 3 9 4,输出结果,44,ppt精选版,动态规划的递推写法,对比递归和递推写法：,递归,也可实现（即从,dp11,开始递归，直至到达边界时返回结果）。是,自顶向下,（,Top-down Approach,），即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。,递推,是,从底向上,（,Bottom-up Approach,），即从边界开始，不断向上解决问题，直到解决了目标问题。,概念,：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有,最优子结构,（,Optimal Substructure,）。,ppt精选版,可以使用动态规划的条件,一个问题必须拥有,重叠子问题,和,最优子结构,，才能使用,动态规划,去解决。,ppt精选版,分治与动态规划,相同点：将问题分解为子问题，然后合并子问题的解得到原问题的解。,不同点：,分治,的子问题,不重叠,。,动态规划,的问题拥有,重叠,子问题。,例如：归并排序和快速排序都分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此他们使用的都是分治法。另外，分治法解决的问题不一定是最优化问题，而动态规划解决的问题一定是最优化问题。,ppt精选版,贪心与动态规划,相同点：要求原问题必须有最优子结构。,不同点：贪心法的计算方式“自顶向下”，但并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题直接抛弃。这种所谓“最优选择”的正确性需要用归纳法证明。而动态规划不管是采用自底向上还是自顶向下的计算方式，都是从边界开始向上得到目标问题的解（即考虑所有子问题）。,贪心：壮士断腕的决策，只要选择，绝不后悔。,动态规划：要看哪个选择笑到最后，暂时领先说明不了问题。,ppt精选版,最大连续子序列和,【,问题描述,】,给定一个数字序列,A1,A2,An,求,i,j(1=i=j=n),使得,Ai+Aj,最大，输出这个最大和。,【,样例,】,输入：,-2 11-4 13-5-2,输出：,20,ppt精选版,步骤,1,：令状态,dpi,表示以,Ai,作为末尾的连续序列的最大和（,Ai,必须作为末尾）。,那么,dp0=-2,dp1=11,dp2=7 (11+(-4)=7),dp3=20 (11+(-4)+13=20),dp4=15 (11+(-4)+13+(-5)=15),dp5=13 (11+(-4)+13+(-5)+(-2)=13),于是转换成求,dp0,dp1,dpn-1,中的最大值，想办法求解,dp,数组。,原序列：,-2 11-4 13-5-2,ppt精选版,步骤,2,：因为,dpi,以,Ai,结尾的连续序列，那么只有两种情况：,这个最大和的连续序列只有一个元素，即,Ai,。,dpi=Ai,这个最大和的连续序列有多个元素，即从前面某处,Ap,开始,(pi),，一直到,Ai,结尾。,dpi=dpi-1+Ai,状态转移方程：,dpi=maxAi,dpi-1+Ai,边界,dp0=A0,，从小到大枚举,i,，即可得到整个,dp,数组。,ppt精选版,#include,#include,#include,#include,using namespace std;,const int maxn=10010;,int Amaxn,dpmaxn;/Ai,存放序列，,dpi,存放以,Ai,结尾的连续序列的最大和,int main(),int n;,scanf(%d,for(int i=0;in;i+)/,读入序列,scanf(%d,/,边界,dp0=A0;,ppt精选版,for(int i=1;in;i+),/,状态转移方程,dpi=max(Ai,dpi-1+Ai);,/dpi,存放以,Ai,结尾的连续序列的最大和，需要遍历,i,得到最大的才是结果,int k=0;,for(int i=1;idpk),k=i;,printf(%dn,dpk);/coutdpk)endl;,system(pause);,return 0;,ppt精选版,状态的无后效性,当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。,即每次计算状态dpi，都只会设计dpi-1，而不直接用到dpi-1蕴含的历史信息。,ppt精选版,动态规划核心,对动态规划可解的问题来说，总会有很多设计状态的方式，,但并不是所有状态都具有无后效性,，因此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。事实上，,如何设计状态和状态转移方程，才是动态规划的核心，而它们也是动态规划最难的地方,。,ppt精选版,问题,A:,最大连续子序列,（时间限制,:1 Sec,内存限制,:32 MB,）