一、动态规划法的基本要素      最优子结构性质：最优子结构性质——用动态规划法求解的前提。当一个问题的最优解中包含了其子问题的最优解时，称该问题具有最优子结构性质。     重叠子问题性质：（递归算法求解问题时）每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题重叠性质。     二、动态规划法求解思路——自底向上、保存子问题的解  三、动态规划法求解步骤      1）刻画最优解的结构特性     2）递归定义最优解值     3）以自底向上方式计算最优解值     4）根据计算得到的信息构造一个最优解     四、动态规划法与分治法的比较  共同点：  将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。  都是求解最优化问题；都具有最优子结构性质。  不同点：  1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。  2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。  3、求解方式不同：  动态规划法：自底向上；  贪心法：自顶向下。以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。  4、对子问题的依赖不同：  动态规划法：依赖于各子问题的解。只有在解出相关子问题后,才能作出选择；应使各子问题最优，才能保证整体最优；  贪心法：不依赖于子问题的解。仅在当前状态下作出最好选择，即局部最优选择。  五、多段图问题      向前递推式     向后递推式     结点的cost和d值求解过程     最短路径长度，并根据d值构造最短路径     注意：d[j] 的含义和最短路径的构造。     课后习题 7-1，7-2     六、关键路径问题     earliest、latest的递推式和求解过程   事件i可能的最早发生时间earliest(i)：指从开始结点 s 到结点 i 的最长路径(关键路径)长度。   事件i允许的最迟发生时间latest(i)：指在不影响工期的条件下,事件(结点) i 允许的最晚发生时间；等于 earliest(n-1) 减去从结点 i 到结点 n-1 的最长路径长度。   寻找关键活动：若 latest(j)-earliest(i)=w(i,j)，则边<i,j>代表的活动是关键活动。   构造关键路径：关键活动组成的关键路径上每个结点 (i和j) 都有 latest(i)=earliest(i) 。   最长路径长度——完成工程的最短时间   程序实现   性能分析：关键路径算法与拓扑排序有相同的时间复杂度，其时间复杂度为 O(n+e)。   补充题   注意：应由关键活动<i,j>（而不是事件i）来确定关键路径。    七、费洛伊德算法     dk 数组和 pathk 数组更新的递推式   每次迭代后的d数组和path数组元素值   程序实现和时间复杂度：O(n^3)    八、最长公共子序列（LCS）      c和s数组元素的求解递推式： 导出序列Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最长公共子序列的递推关系： ⑴若xi=yj，则先求Xi-1和Yj-1的最长公共子序列，并在其尾部加上xi便得到了Xi和Yj的最长公共子序列； ⑵若xi≠yj，则必须分别求解两个子问题Xi-1和Yj以及Xi和Yj-1的最长公共子序列，这两个公共子序列中的较长者就是Xi和Yj的最长公共子序列。     c和s数组元素求值，得最优解值     证明回溯构造最优解     程序实现：时间复杂度为O(m*n)     课后习题7-9     九、备忘录方法  1）动态规划法的变形。 2）采用分治法的思想。 3）自顶向下直接递归的方式求解。 ——两者的异同和适用场合  备忘录方法与动态规划法比较  1、与动态规划法的共同点：用一个表格来保存已求解的子问题的答案，使下次需要解此子问题时，只简单地查看答案，不重新计算。  2、与动态规划法的区别：备忘录的递归方式是自顶向下，而动态规划法的递归方式是自底向上。  备忘录方法与递归方法比较  1、与递归方法的共同点：递归方式均为自顶向下  2、与递归方法的区别：备忘录方法用一个表格来保存已求解的子问题的答案，使下次需要解此子问题时，只简单地查看答案，不重新计算；而递归方法在每次遇到子问题都要重新计算。  如何选择使用动态规划法或备忘录法？      当一个问题的所有子问题都至少要解一次时，选用动态规划法较好，此时没有任何多余的计算，还可利用规则的表格存取方式，减少时间和空间需求。     当一个问题只有部分子问题需要求解时，选用备忘录法较好，它只解那些确实需要求解的子问题。     十、0/1背包      0/1背包问题动态规划法求解——自底向上     0/1背包问题具有最优子结构特性：     设(x0,x1,…,xn-1)，xi∈{0,1} 是0/1背包的最优解。那么(x0,x1,…,xn-2)必然是0/1背包子问题的最优解。     0/1背包问题（实数重量）阶跃点集合求解——非启发式方法、启发式方法 注意：被支配的阶跃点和所有X>M的阶跃点均应该去除。   课后习题7-15、补充题   实验补充——装载问题。