动态规划 动画演示.pptVIP

ACM组 李燮鸣 动态规划 ACM组 李燮鸣 动态规划的家世 身份： 运筹学的一只手 父亲： 20世纪50年代初美国数学家 出生年份： 1957年 户口： 名著《Dynamic Programming》 动态规划的特长： 最短路线 最大公字串 权值三角形 ……. 例题 一个楼梯有N级，每次走一级或两级，从地面（0级）走到顶一共有多少种走法？ 题目分析： 假设从最底下走到第N阶有f(N)种走法。 到达N阶有两种走法 从N-2阶走两步到第N阶，有f(N-2)种方法 从N-1阶走一步到第N阶，有f(N-1)种方法 f(N)=f(N-1)+f(N-2) 显然f(1)=1且f(0)=1 (整形返回值) 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;} 动态规划小结 实质: 通过开辟记录表 记录已求解过的结果 再次求解的时，直接到记录表中去查找 避免重复计算子问题、达到降低时间复杂度的效果。 一个空间换时间的算法 动态规划，通常可以把指数级的复杂度降低到多项式级别。 动态规划小结 难点:写出递推式 步骤其实是很固定的， 递推式如何下手得到会因不同的问题而不同 只要存在重复的子问题都可以使用动态规划的思路，就看你的重复的子问题是不是多的值得使用空间来换时间这个思路了。 谢谢！ * * 输入样例: 3 5 0 输出样例: 3 8 f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) f(1) f(0) 伪代码 f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) f(1) f(0) f(0) f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) f(1) f(0) f(0) Result[0] Result[1] Result[2] Result[3] Result[4] Result[5] -1 -1 -1 -1 -1 -1 1 1 2 3 5 8 开辟一个 int Result[N] 数组，用于存储子问题的解， 初始值为-1 由题意可知，f(n)的值不肯能为负数故可以用负数标示该子问题未解 伪代码 *