（精）北京大学程序设计实习课程.ppt

程序设计实习2007 程序设计实习第九讲 动态规划 主讲教师：田永鸿 yhtian@ /cpp2008/tyh/tyh.htm /jiaoxue-CPP/cpp08.htm 2008年3月24日 内容提要 为什么要用动态规划的方法 递归程序转化为动态规划程序 例题 作业 树形递归 例1：POJ 2753 Fibonacci数列 1，1，…，f(n-1)+f(n-2),… int f(int n){ if(n==0 || n==1) return n; return f(n-1)+f(n-2); } POJ 2753 Fibonacci数列 int f[n+1]; f[1]=f[2]=1; int i; for(i=3;i=n;i++) f[i] = f[i-1]+f[i-2]; cout f[n] endl; 用空间换时间 - 动态规划 什么是动态规划？ 动态规划是求解包含重叠子问题的最优化方法 基本思想：将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解（注意：不是简单分而治之）。 只能应用于有最优子结构的问题（即局部最优解能决定全局最优解，或问题能分解成子问题来求解）。 计算机科学与工程、管理科学（运筹学）等领域中许多算法的基础，如最短路径、背包问题、项目管理、网络流优化等。 什么是动态规划？ 动态规划的性质 最优化子结构性质。若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理） 能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的 子问题重叠性质。在用递归算法自顶向下对问题进行求解是，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。 动态规划的实质就是 动规的要诀－状态 用动态规划解题，关键是要找出“状态”，和在“状态”间进行转移的办法（即状态转移方程） 我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。 动态规划 例2　POJ 1163 数字三角形 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100 数字为 0 - 99 POJ 1163 输入格式： //三角形行数。下面是三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 要求输出最大和 解题思路 算法一：递归的想法 设f(i,j) 为三角形上从点(i,j)出发向下走的最长路经，则f(i,j) = max(f(i+1,j), f(i+1,j+1)) 要输出的就是f(0,0)即从最上面一点出发的最长路经。 解题思路 以D(r, j)表示第r行第 j 个数字，以MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的各条路径中，数字之和最大的那条路径的数字之和，则本题是要求MaxSum(0,0) 。（假设行编号和一行内数字编号都从0开始)。 典型的动态规划问题。 从某个D(r, j)出发，显然下一步只能走D(r+1,j)或者D(r+1, j+1)，所以，对于N行的三角形： if ( r == N-1 ) MaxSum(r,j) = D(N-1,j) else MaxSum(r, j) = Max(MaxSum(r+1,j), MaxSum(r+1,j+1) ) + D(r,j); #include iostream.h #define MAX 101 int triangle[MAX][MAX]; int n; int longestPath(int i, int j); void main(){ 　int i,j; 　cin n; 　for(i=0;in;i++) for(j=0;j=i;j++) 　　 cin triangle[i][j]; 　cout longestPath(0,0) endl; } int longestPath(int i, int j){ 　if(i==n-1) return triangle[i][j]; 　int x = longestPath(i+1,j); 　int y = longestPath(i+1,j+1); if(xy) x=y; return x+triangle[i][j]; } 　　　　　　　　　　　　 为什么超时？ 讨论 为什么超时？ 回答：重复计算 一种可能的改