动态规划(朱全民).ppt

动态规划参与竞赛的同学应由竞争关系和独立关系(你做你的,我干我的,程序和算法互相保密,彼此津津乐道于对方的失败和自己的成功)转向合作学习的关系(通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务)2斐波纳契数列F(n)3递归vs动态规划递归版本:F(n)1 ifn=0orn=1then2 return13 else4 returnF(n-1)+F(n-2)动态规划:F(n)1 A[0]=A[1]←12 fori←2tondo3 A[i]←A[i-1]+A[i-2]4 returnA[n]太慢!有效率!算法复杂度是O(n)4方法概要构造一个公式,它表示一个问题的解是与它的子问题的解相关的公式.(n)=F(n-1)+F(n-2).为这些子问题做索引,以便它们能够在表中更好的存储与检索(.,数组array【】)以自底向上的方法来填写这表格;,,我们称这种方法为:(计算机普及很少时),这些规划设计是与”列表“,并存储子问题的解而避免计算重复的子问题,并由子问题的解得到原问题的解。动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法的基本要素:最优子结构性质和重叠子问题。6最优子结构性质:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。对每个子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。(最优,最大,最小,最长……)问题;,可以分解(划分阶段)的;,即可以由(n-1)的最优推导出n的最优8动态规划算法的4个步骤:.(一维,二维,三维数组).(状态转移方程)(n)步骤1:用F(n)表示在斐波纳契数列中第n个数的值;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解步骤4:在数组中分析构造出问题的解;,求出n!步骤1:用F(n)表示n!的值;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解