动态规划 动画演示 加长版.pptVIP

动态规划 黑龙江大学 计算机科学技术学院07级 计算机科学技术学院科协 ACM组 risyomei@ 李燮鸣 声明 本ppt只是个人对动态规划的一些看法, 有不足和缺漏之处请谅解和及时地指出.欢迎给我发送E-mail，进行探讨 在讲解的过程中，若有不明白的地方，欢迎随时打断我！ 动态规划的家世 身份： 运筹学分支 出生年份： 1957年 父亲： 20世纪50年代初美国数学家 户口： 名著《Dynamic Programming》 动态规划的特长： 最短路线 最大公字串 权值三角形 ……. “一个原则，两个基本点” (原创) 原则： 不计算重复的子问题 基本点： (1)最优子结构性质 (2)子问题重叠性质 动态规划两种实现 递归实现 循环实现 大家对递归的了解程度 例题1 一个楼梯有N级，每次走一级或两级，从地面（0级）走到第N级一共有多少种走法？ 题目分析： 假设第0阶到第N阶有f(N)种走法。 (整形返回值) 0阶到n阶的走法(整形参数 n) { 如果n==1或者n==0那么直接返回1 否则： 返回 0阶到n-2阶的走法+0阶到n-1阶的走法 } 纯递归代码 #include iostream.h int f(int n) { if(n==0||n==1) return 1; //如果求解f(0)或f(1)则返回1 else return f(n-1) + f(n-2); } int main() { int n; while(cinnn!=0) //执行循环直到输入0 coutf(n)endl; return 0; } (整形返回值) 0阶到n阶的走法(整形参数 n) { 如果“0阶到n阶的走法”已经被求解：直接返回它的答案 否则： 如果n==1或者n==0那么 答案为1 否则： 答案为“ 0阶到n-2阶的走法”+“0阶到n-1阶的走法” 保存答案； 返回答案； } #include iostream.h #include memory.h int result[100]; int f(int n) { if(result[n]=0) return result[n];//如果该问题已经求解过，则不再求解 int res; if(n==0||n==1) res= 1; else res = f(n-1) + f(n-2); result[n] = res;//存储求出来的解 return res; } int main() { int n; while(cinnn!=0) //执行循环直到输入0 { memset(result,-1,sizeof(result)); coutf(n)endl; } return 0;} 例题2POJ 1163:The Triangle Input Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is 1 but = 100. The numbers in the triangle, all integers, are between 0 and 99. Output Your program is to write to standard output. The highest sum is written as an integer. Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 非动态规划的解决方法 动态规划的解决方法 #include stdio.h int data[110][110]; int main() { int N,i,j; scanf(%d,N); for(i=0;iN;i++) for(j=0;j=i;j++) scanf(%d,data[i][j]); for(j=N-2;j=0;j--) for(i=0;i=j;i++) else data[j][i]+=(data[j+1][i]data[j+1][i+1]?data[j+1][i]:data[j+1][i+1]);