文档介绍：动态规划*F(n)=1 ifn=0or1F(n-1)+F(n-2) ifn>1n0**********F(n)1123581321345589斐波纳契数列F(n)*递归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)*方法概要构造一个公式,它表示一个问题的解是与它的子问题的解相关的公式. (n)=F(n-1)+F(n-2).为这些子问题做索引,以便它们能够在表中更好的存储与检索(.,数组array【】)以自底向上的方法来填写这表格;,,我们称这种方法为:(计算机普及很少时), 这些规划设计是与”列表“方法相关的.*动态规划算法算法思想将待求解的问题分解成若干个子问题,并存储子问题的解而避免计算重复的子问题,并由子问题的解得到原问题的解。动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法的基本要素:最优子结构性质和重叠子问题。原理*最优子结构性质:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。对每个子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。原理*(最优,最大,最小,最长……)问题;,可以分解(划分阶段)的;,即可以由(n-1)的最优推导出n的最优原理*动态规划算法的4个步骤:.(一维,二维,三维数组).(状态转移方程)*(n)F(n)=1 ifn=0or1F(n-1)+F(n-2) ifn>1步骤1:用F(n)表示在斐波纳契数列中第n个数的值;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解n0**********F(n)1123581321345589步骤4:在数组中分析构造出问题的解;*,求出n!F(n)=1 ifn=0or1F(n-1)*n ifn>1步骤1:用F(n)表示n!的值;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解n0**********F(n)1**********实例