区间树及动态规划

定理14.2

循环不变式证明 查找算法的正确性

动态规划

分治法中：分解的子问题 大量重叠时，此时分治法效率不高。

Programming 其实不是编程，是查表。

• 最优解可以是不唯一的，是一个集合

• 最优解值是唯一的，是边数，在求最短路径举例中

• 递归是从上往下计算，因此会产生很多重复计算

第1步是最关键的，也是最困难的。

动态规划的方法本质上是一种查表的方法。

上面这个子问题有2n个。 上图中fij是二维数组。

step3 也重要，底错了就全错了。

对于这个问题，分治法从上到下是2的n次方的下界。

要得到(输出)最优解，step4.

通过辅助数组，反向输出。