教案8动态规划法.pdfVIP

动态规划 Dynamic Programming 一、动态规划的基本思想 如果各个⼦问题不是独⽴的，不同的⼦问 题的个数只是多项式量级，如果我们能够 保存已经解决的⼦问题的答案，⽽在需要 的时候再找出已求得的答案，这样就可以 避免⼤量的重复计算。由此⽽来的基本思 路是，⽤⼀个表记录所有已解决的⼦问题 的答案，不管该问题以后是否被⽤到，只 , 要它被计算过，就将其结果填⼊表中以避 免重复计算。 动态规划的基本思想 n  简单地说，动态规划依然是把⼀个⼤问题分为若干性 质相同的⼦问题，⽽这些⼦问题⾥⾯会有若干的重叠。 为了当出现⼦问题重叠的时候不重复运算。我们就需 要把所有的已经求出的⼦问题都存下来，判断这个⼦ 问题是否已经算过，算过了就不要再算了。如果没算 过就算⼀遍下次在遇到这个⼦问题就可以不算了。 n  因此我们必须开出⼀个数组来存储，则动态规划算法 可以节省⼤量的时间。假设所有的⼦问题都不重叠它 的时间复杂度会和递归⼀样。⽽如果优有⼤量的⼦问 题重叠，那么会发现时间复杂度会有明显的降低。可 以提⾼运算效率，缩短运算时间。 n  动态规划：空间换时间的算法。 二、动态规划的基本步骤 动态规划算法通常用于求解具有某种 最优性质的问题。在这类问题中，可能 会有许多可行解。每一个解都对应于一 个值，我们希望找到具有最优值（最大 值或最小值）的那个解。设计一个动态 规划算法，通常可以按以下几个步骤进 行： 基本步骤 （1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4 ）根据计算最优值时得到的信息，构造一个最优解。 其中（1）－（3）步是动态规划算法的基本步骤。在只 需要求出最优值的情形，步骤（4 ）可以省去。若需要 求出问题的一个最优解，则必须执行步骤（4 ）。此时， 在步骤（3）中计算最优值时，通常需记录更多的信息， 以便在步骤（4 ）中，根据所记录的信息，快速构造出 一个最优解。 三、动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具有 的两个重要性质： 1、最优子结构：当问题的最优解包含了其子问 题的最优解时，称该问题具有最优子结构性质。 2、重叠子问题：在用递归算法自顶向下解问题 时，每次产生的子问题并不总是新问题，有些子 问题被反复计算多次。动态规划算法正是利用了 这种子问题的重叠性质，对每一个子问题只解一 次，而后将其解保存在一个表格中，在以后尽可 能多地利用这些子问题的解。 改进 递归：由上自下 递推：由下自上 n  将递归改为递推，这样可以减少递归调 用的开销。 n  这种高效算法，就是动态规划算法。 问题1 Fibonacci斐波那契数列问题 0 n=0 F (n)= n=1 F (n-1)+F (n-2) n1 递归 int fibo(int n) { if(n 1||n 2) return 1; else return (fibo(n-1)+fibo(n-2)); } 动态规划 int f[1000]; int fibo(int n) { if(n2) return 1; if(f[n]!= 0)