提高篇——动态规划专题.ppt

提高篇动态规划专题,动态规划递归递推,一种精妙的算法思想。特点：没有固定的写法具体问题具体分析需要：多练习、多思考、多总结,什么是动态规划,最优化问题,1,复杂问题,2,分解子问题,3,记录每个解,4,DynamicProgramming,动态规划是一种用来解决一类最优化问题的算法思想。将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来，这样可以提高计算效率，但不能说这种做法就是动态规划的核心。,动态规划的递归写法,【理解】如何记录子问题的解，来避免下次遇到相同的子问题时的重复计算。,斐波那契数列：F0=1,F1=1,Fn=Fn-1+Fn-2(n=2),intF(intn)if(n=0|n=1)return1;elsereturnF(n-1)+F(n-2);,一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处又称作记忆化搜索。,缺点：重复计算。当n=5时，F(5)=F(4)+F(3),接下来计算F(4)=F(3)+F(2),这样F(3)就被计算了两次。如果n很大，时间复杂度会高达O(2n)。,避免重复计算,开一个一维数组dp，用于保存已经计算过的结果，其中dpn记录F(n)的结果，并用dpn=-1表示F(n)当前还没有被计算过。intdpmaxn;intF(intn)if(n=0|n=1)return1;/递归边界if(dpn!=-1)returndpn;/已经计算过，直接返回结果，不再重复计算elsedpn=F(n-1)+F(n-2);/计算F(n)，并保存至dpnreturndpn;/返回F(n)的结果,记忆化搜索,时间复杂度O(2n)降到了O(n),时间复杂度对比图,斐波那契数列递归图O(2n),斐波那契数列记忆化搜索O(n),重叠子问题（OverlappingSubproblems）,如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。一个问题必须拥有重叠子问题，才能使用动态规划去解决。,动态规划的递推写法,动态规划的递推写法,如果开一个二维数组f，其中fij存放第i层的第j个数字，那么就有f11=5,f21=8,f22=3,f31=12,f54=9,f55=4。如果尝试穷举所有路径，然后记录路径上的数字和的最大值，那么由于每层中的每个数字都会有两条分支路径，因此时间复杂度为O(2n)，这在n很大的情况下是不可以接受的。那么，产生这么大复杂度的原因是什么？从5出发，按587的路线来到7，并枚举从7出发的到达最底层的所有路径。但是，之后当按537的路线再次来到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,动态规划的递推写法,归纳：如果要求出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(1n;for(inti=1;ifij;/输入数塔for(intj=1;j=1;i-)for(intj=1;j=i;j+)dpij=max(dpi+1j,dpi+1j+1)+fij;/动态转移方程coutdp11endl;return0;,动态规划的递推写法,输入数据55831271641011695394,输出结果44,动态规划的递推写法,对比递归和递推写法：递归也可实现（即从dp11开始递归，直至到达边界时返回结果）。是自顶向下（Top-downApproach），即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。递推是从底向上（Bottom-upApproach），即从边界开始，不断向上解决问题，直到解决了目标问题。,概念：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构（OptimalSubstructure）。,可以使用动态规划的条件,一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。,分治与动态规划,相同点：将问题分解为子问题，然后合并子问题的解得到原问题的解。不同点：分治的子问题不重叠。动态规划的问题拥有重叠子问题。例如：归并排序和快速排序都分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此他们使用的都是分治法。另外，分治法解决的问题不一定是最优化问题，而动态规划解决的问题一定是最优化问题。,贪心与动态规划,相同点：要求原问题必须有最优子结构。不同点：贪心法的计算方式“自顶向下”，但并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题直接抛弃。这种所谓“最优选择”的正确性需要用归纳法证明。而动态规划不管是采用自底向上还是自顶向下的计算方式，都是从边界开始向上得到目标问题的解（即考虑所有子问题）。贪心：壮士断腕的决策，只要选择，绝不后悔。动态规划：要看哪个选择笑到最后，暂时领先说明不了问题。,最大连续子序列和,【问题描述】给定一个数字序列A1,A2,An,求i,j(1=i=j=n),使得Ai+Aj最大，输出这个最大和。【样例】输入：-211-413-5-2输出：20,步骤1：令状态dpi表示以Ai作为末尾的连续序列的最大和（Ai必须作为末尾）。,那么dp0=-2dp1=11dp2=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数组。,原序列：-211-413-5-2,步骤2：因为dpi以Ai结尾的连续序列，那么只有两种情况：,这个最大和的连续序列只有一个元素，即Ai。dpi=Ai这个最大和的连续序列有多个元素，即从前面某处Ap开始(pi)，一直到Ai结尾。dpi=dpi-1+Ai状态转移方程：dpi=maxAi,dpi-1+Ai边界dp0=A0，从小到大枚举i，即可得到整个dp数组。,#include#include#include#includeusingnamespacestd;constintmaxn=10010;intAmaxn,dpmaxn;/Ai存放序列，dpi存放以Ai结尾的连续序列的最大和intmain()intn;scanf(%d,for(inti=1;idpk)k=i;printf(%dn,dpk);/coutdpk)endl;system(pause);return0;,状态的无后效性,当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。即每次计算状态dpi，都只会设计dpi-1，而不直接用到dpi-1蕴含的历史信息。,动态规划核心,对动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有状态都具有无后效性，因此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。事实上，如何设计状态和状态转移方程，才是动态规划的核心，而它们也是动态规划最难的地方。,问题A:最大连续子序列（时间限制:1Sec内存限制:32MB）,题目描述给定K个整数的序列N1,N2,.,NK，其任意连续子序列可表示为Ni,Ni+1,.,Nj，其中1=i=j=K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列-2,11,-4,13,-5,-2，其最大连续子序列为11,-4,13，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。输入测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K(KAi;intans=-1;/记录最大的dpifor(inti=1;i=Aj/状态转移方程，用以更新dpi,ans=max(ans,dpi);coutansendl;return0;,问题A:最长上升子序列（2Sec64MB）,题目描述一个数列ai如果满足条件a1a2.aN，那么它是一个有序的上升数列。我们取数列(a1,a2,.,aN)的任一子序列(ai1,ai2,.,aiK)使得1=i1i2.iK=N。例如，数列(1,7,3,5,9,4,8)的有序上升子序列，像(1,7)，(3,4,8)和许多其他的子序列。在所有的子序列中，最长的上升子序列的长度是4，如(1,3,5,8)。现在你要写一个程序，从给出的数列中找到它的最长上升子序列。输入输入包含两行，第一行只有一个整数N（1=N=1000），表示数列的长度。第二行有N个自然数ai，0=ai=10000，两个数之间用空格隔开。输出输出只有一行，包含一个整数，表示最长上升子序列的长度。样例输入71735948,样例输出4,最长公共子序列（LCS）,给定两个字符串（或数字序列）A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）。样例：如样例所示，字符串“sadstory”与“adminsorry”的最长公共子序列为“adsory”，长度为6。,令dpij表示字符串A的i号位和字符串B的j号位之前的LCS长度（下标从1开始），如dp45表示“sads”与“admin”的LCS长度。那么可以根据Ai和Bj的情况，分为两种决策：（1）若Ai=Bj，则字符串A与字符串B的LCS增加了1位，即有dpij=dpi-1j-1+1。（2）若Ai!=Bj，则字符串A的i号位和字符串B的j号位之前的LCS无法延长，因此dpij将会继承dpi-1j与dpij-1中的较大值，即有dpij=maxdpi-aj，dpij-1。,状态转移方程：,边界：dpi0=dp0j=0(0=i=n,0=i=m)时间复杂度：O(nm)输入数据：sadstoryadminsorry,输出结果：6,最长回文子串,给出一个字符串S，求S的最长回文子串的长度。样例：字符串“PATZJUJZTACCBCC”的最长回文子串为“ATZJUJZTA”，长度为9。,最长回文子串,是否能转换为最长公共子序列（LCS）来求解？把字符串S倒过来变成字符串T，然后对S和T进行LCS模型求解，得到的结果就是需要的答案。,一旦S中同时存在一个子串和它的倒序，那么答案就会出错。例如字符串S=“ABCDZJUDCBA”，将其倒过来之后变成T=“ABCDUJZDCBA”，这样得到最长公共子串为”ABCD”，长度为4，事实上S的最长回文子串长度为1。,令dpij表示Si至Sj所表示的子串是否是回文子串，是则为1，不是为0。这样根据Si是否等于Sj，可以把转移情况分为两类：（1）若Si=Sj，那么只要Si+1至Sj-1是回文子串，Si至Sj就是回文子串；如果Si+1至Sj-1不是回文子串，则Si至Sj也不是回文子串。（2）若Si!=Sj，那么Si至Sj一定不是回文子串。,状态转移方程：,边界：dpij=1,dpii+1=(Si=Si+1)?1:0时间复杂度：O(n2)存在问题：如果按照i和j从小到大的顺序来枚举子串的两个端点，然后更新dpij，会无法保证dpi+1j-