05_ACM动态规划

ACM动态规划主讲人：李欣湖南工业大学工大ACM团队递归一般每个可以使用递归算法求解的题目都可以写出一个递归函数。题目的主要问题就是把一个大问题转换为若干个性质相同的子问题。注意是性质相同，因为只有性质相同我们才能使用同一个函数来表示。求解的过程是从最后一步，当然每一步都会用到比自己要小的子问题的值，那么要调用程序来求出这些子问题的解，一步步返回最后得到最后的问题的解。也可以理解为求解过程是“反向”的。因为变量会是逐渐变小的。递归是自顶向下逐步扩展，最后自下向顶运算。求N!:F(n)扩展到f(1),再由f(1)逐步算回到f(n)湖南工业大学工大ACM团队动态规划动态规划算法可以理解为是递归算法的一个延伸。单纯的递归算法是会出现很多子问题的重叠的，这样还是会造成同一问题的重复运算。所以我们要找一个办法来避免重复的运算。于是就出现了动态规划。简单地说，动态规划依然是把一个大问题分为若干性质相同的子问题，而这些子问题里面会有若干的重叠。为了当出现子问题重叠的时候不重复运算。我们就需要把所有的已经求出的子问题都存下来，判断这个子问题是否已经算过，算过了就不要再算了。如果没算过就算一遍下次在遇到这个子问题就可以不算了。因此我们必须开出一个数组来存储，则动态规划算法可以节省大量的时间。假设所有的子问题都不重叠它的时间复杂度会和递归一样。而如果优有大量的子问题重叠，那么会发现时间复杂度会有明显的降低。可以提高运算效率，缩短运算时间。动态规划：空间换时间的算法。湖南工业大学工大ACM团队0n=0F(n)=1n=1F(n-1)+F(n-2)n1Fibonacci斐波那契数列问题递归与动态规划湖南工业大学工大ACM团队递归算法intfibo(intn){if(n==1||n==2)return1;elsereturn(fibo(n-1)+fibo(n-2));}湖南工业大学工大ACM团队思考用动态规划如何解决?湖南工业大学工大ACM团队动态规划算法将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。算法思想湖南工业大学工大ACM团队动态规划算法用空间换时间intfibo(intn){if(n2)return1;if(f[n]!=0)returnf[n];elsef[n]=fibo(n-1)+fibo(n-2);returnf[n];}//注意n=46达到18亿多思考：POJ3070湖南工业大学工大ACM团队数字三角形(grids2760)问题描述738810274445265上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。湖南工业大学工大ACM团队数字三角形(grids2760)输入数据输入的第一行是一个整数N(1N=100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。输出要求输出最大的和。输入样例5738810274445265输出样例30湖南工业大学工大ACM团队试想一下：这道题如果用蛮力法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^310^9=10亿）。湖南工业大学工大ACM团队考虑一下：从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。湖南工业大学工大ACM团队解题思路D(r,j):第r行第j个数字(r,j都从1开始算)MaxSum(r,j):从第r行的第j个数字到底边的最佳路径的数字之和。从某个D(r,j)出发，显然下一步只能走D(r+1,j)或者D(r+1,j+1)如果走D(r+1,j)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j)+D(r,j)；如果走D(r+1,j+1)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j+1)+D(r,j)。选择往哪里走，就看MaxSum(r+1,j)和MaxSum(r+1,j+1)哪个更大了。湖南工业大学工大ACM团队解题思路MaxSum(1,1)MaxSum(2,1)MaxSum(2,2)MaxSum(3,1)MaxSum(3,2)MaxSum(3,2)MaxSum(3,3)M(4,1)M(4,2)M(4,2)M(4,3)M(4,2)M(4,3)M(4,3)M(4,4)湖南工业大学工大ACM团队核心代码intMaxSum(intr,intj){if(r==N)returnD[r][j];intnSum1=MaxSum(r+1,j);intnSum2=MaxSum(r+1,j+1);if(nSum1nSum2)returnnSum1+D[r][j];returnnSum2+D[r][j];}湖南工业大学工大ACM团队核心代码-存在的问题上面的程序，效率非常低，在N值并不大，比如N=100的时候，就慢得几乎永远算不出结果了。为什么会这样呢？是因为过多的重复计算。不妨将对MaxSum函数的一次调用称为一次计算。那么，每次计算MaxSum(r,j)的时候，都要计算一次MaxSum(r+1,j)，而每次计算MaxSum(r,j+1)的时候，也要计算一次MaxSum(r+1,j)。重复计算因此产生。在题目中给出的例子里，如果我们将MaxSum(r,j)被计算的次数都写在位置（r,j），那么就能得到下面的三角形：111121133114641从上图可以看出，最后一行的计算次数总和是16，倒数第二行的计算次数总和是8。不难总结出规律，对于N行的三角形，总的计算次数是20+21+22……2N-1=2N-1。当N=100时，总的计算次数是一个让人无法接受的大数字。湖南工业大学工大ACM团队核心代码-解决方案问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r,j)的值时，就将该值存放起来，下次再需要计算MaxSum(r,j)时，直接取用存好的值即可，不必再次调用MaxSum进行函数递归计算了。每个MaxSum(r,j)都只需要计算1次即可总的计算次数（即调用MaxSum函数的次数）就是三角形中的数字总数，即1+2+3+……N=N(N+1)/2如何存放计算出来的MaxSum（r,j）值呢？显然，用一个二维数组aMaxSum[N][N]就能解决。aMaxSum[r][j]就存放MaxSum(r,j)的计算结果。需要MaxSum(r,j)的值时，不必再调用xSum函数，只需直接取aMaxSum[r][j]的值即可。湖南工业大学工大ACM团队核心代码-动态规划intMaxSum(intr,intj){if(r==N)returnD[r][j];if(aMaxSum[r+1][j]==-1)//如果MaxSum(r+1,j)没有计算过aMaxSum[r+1][j]=MaxSum(r+1,j);if(aMaxSum[r+1][j+1]==-1)//如果MaxSum(r+1,j+1)没有计算过aMaxSum[r+1][j+1]=MaxSum(r+1,j+1);if(aMaxSum[r+1][j]aMaxSum[r+1][j+1])returnaMaxSum[r+1][j]+D[r][j];returnaMaxSum[r+1][j+1]+D[r][j];}湖南工业大学工大ACM团队动态规划的定义这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。湖南工业大学工大ACM团队由下往上递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式。思考：不需要写递归函数从aMaxSum[N-1]这一行元素开始向上逐行递推，就能求得最终MaxSum[1][1]的值了。湖南工业大学工大ACM团队最长上升子序列(Grids2757)问题描述一个数的序列bi，当b1b2...bS的时候，我们称这个序列是上升的。对于给定的一个序列(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).你的任务，就是对于给定的序列，求出最长上升子序列的长度。湖南工业大学工大ACM团队最长上升子序列(Grids2757)输入数据输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。输出要求最长上升子序列的长度。输入样例71735948输出样例4湖南工业大学工大ACM团队解题思路如何把这个问题分解成子问题呢？经过分析，发现“求以ak（k=1,2,3…N）为终点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。湖南工业大学工大ACM团队解题思路由上所述的子问题只和一个变量相关，就是数字的位置k就是“状态”，而状态k对应的“值”，就是以ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有N个。设MaxLen(k)表示以ak做为“终点”的最长上升子序列的长度，那么状态转移方程：MaxLen(1)=1MaxLen(k)=Max{MaxLen(i)：1ik且aiak且k≠1}+1即：MaxLen(k)的值，就是在ak左边，“终点”数值小于ak，且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列，加上ak后就能形成一个更长的上升子序列。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移湖南工业大学工大ACM团队核心代码aMaxLen[1]=1;for(i=2;i=N;i++){//每次求以第i个数为终点的最长上升子序列的长度intnTmp=0;//记录满足条件的，第i个数左边的上升子序列的最大长度for(intj=1;ji;j++){//察看以第j个数为终点的最长上升子序列if(b[i]b[j]){if(nTmpaMaxLen[j])nTmp=aMaxLen[j];}}aMaxLen[i]=nTmp+1;}intnMax=-1;for(i=1;i=N;i++)if(nMaxaMaxLen[i])nMax=aMaxLen[i];printf(%d\n,nMax);湖南工业大学工大ACM团队动态规划问题的特征动态规划算法的有效性依赖于问题本身所具有的两个重要性质：1、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。2、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。