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

《提高篇-动态规划专题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、提高篇——动态规划专题动态规划•递归递推一种精妙的算法思想。特点：没有固定的写法具体问题具体分析需要：多练习、多思考、多总结什么是动态规划最优化问题1复杂问题2分解子问题3记录每个解4DynamicProgramming动态规划是一种用来解决一类最优化问题的算法思想。将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来，这样可以提高计算效率，但不能说这种做法就是动态规划的核心。动态规划的递归写法【理解】如何记录子问题的解，来避免下次遇到相同的子问题时的重复计算。斐波那契数列：F0=1,F1

2、=1,Fn=Fn-1+Fn-2(n>=2)intF(intn){if(n==0

3、

4、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，用于保存已经计算过的结果，其中dp[n]记录F(n)的结果，并用dp[n]=-1表示F(n)当前还没有被计算过。intdp[

5、maxn];intF(intn){if(n==0

6、

7、n==1)return1;//递归边界if(dp[n]!=-1)returndp[n];//已经计算过，直接返回结果，不再重复计算else{dp[n]=F(n-1)+F(n-2);//计算F(n)，并保存至dp[n]returndp[n];//返回F(n)的结果}}记忆化搜索时间复杂度O(2n)降到了O(n)时间复杂度对比图F(5)F(4)F(3)F(2)F(1)F(0)F(1)F(2)F(1)F(0)F(3)F(2)F(1)F(0)F(1)斐波那契数列递归图O(2n)F(5)F(4)F(3)F(2)F(1

8、)F(0)F(1)F(2)F(3)斐波那契数列记忆化搜索O(n)重叠子问题（OverlappingSubproblems）如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。一个问题必须拥有重叠子问题，才能使用动态规划去解决。动态规划的递推写法【数塔问题】将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字……第n层有n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大是多少？5837124910516113694动态规划的递推写法如果开

9、一个二维数组f，其中f[i][j]存放第i层的第j个数字，那么就有f[1][1]=5,f[2][1]=8,f[2][2]=3,f[3][1]=12,……,f[5][4]=9,f[5][5]=4。如果尝试穷举所有路径，然后记录路径上的数字和的最大值，那么由于每层中的每个数字都会有两条分支路径，因此时间复杂度为O(2n)，这在n很大的情况下是不可以接受的。那么，产生这么大复杂度的原因是什么？从5出发，按587的路线来到7，并枚举从7出发的到达最底层的所有路径。但是，之后当按537的路线再次来到7时，又会去枚举从7出发的到达最底层的所有路径，这就导致了从7

10、出发的到达最底层的所有路径都被反复地访问。其实，可以把路径上能产生的最大和记录下来，这样就可以避免重复计算。所以令dp[i][j]表示从第i行第j个数字出发的到达最底层的所有路径中能得到的最大和，例如dp[3][2]就是7的最大和。那么dp[1][1]就是最终答案，现在想办法求出它。注意一个细节：如果要求出“从位置（1,1）到达最底层的最大和”dp[1][1]，那么一定要先求出它的两个子问题“从位置（2,1）到达最底层的最大和dp[2][1]”和“从位置（2,2）到达最底层的最大和dp[2][2]”，即进行了一次决策：走数字5的左下还是右下。于是dp[1][

11、1]就是dp[2][1]和dp[2][2]的较大值加上5。公式：dp[1][1]=max(dp[2][1],dp[2][2])+f[1][1]动态规划的递推写法归纳：如果要求出dp[i][j]，那么一定要求出它的两个子问题“从位置(i+1,j)到达最底层的最大和dp[i+1][j]”和“从位置(i+1,j+1)到达最底层的最大和dp[i+1][j+1]”，即进行了一次决策：走位置(i,j)的左下还是右下。公式：dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j]把dp[i][j]称为问题的状态，公式称为状态转移方程，它把

12、状态dp[i][j]转移为dp[i+1][j]和dp