《dp入门讲解》PPT课件.ppt

《《dp入门讲解》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划入门讲解UESTC陈斐童什么是dynamicprogramming?Dp不是一种算法，而是一种思想。TopDownMethod递归的将问题分解为更小的问题。BottomUpMethod由初始状态递推得到目标状态。Dp的本质是状态和状态转移。做dp题的时候就是定义状态，写出转移方程。Dp的条件是最优子结构和无后效性。不满足这两个条件的，思想又和dp相似的，叫搜索。状态的定义？状态是保存的信息状态要有利于答案的求解状态要容易转移一个简单的例子，dp[n]=dp[n-1]+dp[n-2]两个条件？无后效性状

2、态间的转移与如何到达某状态无关状态定义完整而唯一最优子结构当前状态可以从之前的某个或某些状态直接得到状态转移包含了所有的可能复杂度？时间复杂度：状态数*状态转移数空间复杂度：状态数？例题所有代码仅做演示，肯定是过不了题的。（虽然专题好像没有例题）例题1：数字三角形311276645827341从上往下走，每次可以向左下或右下走一个，直到最下行，问经过数字的和最大是多少？例题1：数字三角形311276645827341贪心？在第二行就迷失了方向例题1：数字三角形311276645827341定义状态dp[i][

3、j]表示当走到第i行，第j个节点，能够得到的最大的和。Ans=max{dp[5][k]},k=1...5例题1：数字三角形311276645827341状态转移:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]dp[i][j]表示当走到第i行，第j个节点，能够得到的最大的和。例题1：数字三角形311276645827341状态转移:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]dp[i][j]表示当走到第i行，第j个

4、节点，能够得到的最大的和。例题1：数字三角形自顶而下(记忆化搜索)dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]例题1：数字三角形自底而上(递推)dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]例题2：最长上升子序列给定一个长度为n(1<=n<=1000)的整数序列a[i]，求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列)，满足如下条件：1、该序列单调递增；2、在所有满足条件1的序列中长度是最长的

5、；例题2：最长上升子序列给定一个长度为n(1<=n<=1000)的整数序列a[i]，求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列)，满足如下条件：1、该序列单调递增；2、在所有满足条件1的序列中长度是最长的；状态定义：dp[i]表示以第i个数结尾的上升子序列最长的长度。状态转移：dp[i]=max{dp[j]}+1其中j=1….i-1,且a[i]>a[j]Ans=max{dp[i]},i=1...n时间复杂度：O(n2)空间复杂度：O(n)例题2：最长上升子序列演示代码例题3：区间dp（

6、POJ3280）给定一个长度为n（n<=1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。例题3：区间dp状态定义：dp[i][j]表示A[i...j]成为回文串需要插入的字符数。注意i>j时表示空串，是回文串，是有意义的。状态转移：A[i]==A[j]时，dp[i][j]=dp[i+1][j-1]A[i]!=A[j]时，我们既可以在A[i]后插入一个A[j]，也可以在A[j]前插入一个A[i]，因此有dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1Ans=dp[1][

7、len]给定一个长度为n（n<=1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。例题3：区间dp演示代码例题4：状压dp（TSP）对于一个节点数<=15的图，要求找到一条路径能够遍历每一个节点一次后返回出发点(Hamiltonianpath)，并且路径距离最短。例题4：状压dp直接枚举所有可能的顺序，O(n!)无法承受。状态定义：//注意这题从0开始计数memo[i][j]i的每一位表示已经经过的点，j表示当前所在的点由于状态转移没有明显的顺序，用记忆化搜索比较好。search(i,j):fo

8、rkinnotvisitednode:search(i

9、(1<