一、动态规划法的基本要素

  • 最优子结构性质：最优子结构性质——用动态规划法求解的前提。当一个问题的最优解中包含了其子问题的最优解时，称该问题具有最优子结构性质。

  • 重叠子问题性质：（递归算法求解问题时）每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题重叠性质。

二、动态规划法求解思路——自底向上、保存子问题的解

三、动态规划法求解步骤

  • 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、补充题
  • 实验补充——装载问题。