设计与分析-动态规划

---

动态规划方法类似于分而治之，将问题分解为更小的可能的子问题。但与分而治之不同的是，这些子问题并不是独立解决的。相反，这些较小的子问题的结果被记住并用于类似或重叠的子问题。

大多数情况下，动态规划算法用于解决优化问题。在解决当前的子问题之前，动态算法将尝试检查先前解决的子问题的结果。将子问题的解进行组合，以获得最佳的最优最终解。因此，该范例被称为使用自下而上的方法。

所以我们可以得出结论 -

• 问题应该能够分为更小的重叠子问题。

• 通过使用较小子问题的最优解可以得到最终的最优解。

• 动态算法使用记忆。

然而，在问题中，两个主要属性表明可以使用动态规划来解决给定问题。他们是 -

重叠子问题

与分治法类似，动态规划也结合了子问题的解决方案。主要用于需要重复求解某一子问题的情况。计算出的解决方案存储在表中，因此不必重新计算。因此，在存在重叠子问题的情况下需要这种技术。

例如，二分查找不存在重叠子问题。而斐波那契数列的递归程序有许多重叠的子问题。

最优子结构

给定问题具有最优子结构性质，如果给定问题的最优解可以使用其子问题的最优解来获得。

例如，最短路径问题具有以下最优子结构属性 -

如果节点 x 位于从源节点u到目的节点v的最短路径中，则从u到v的最短路径是从u到 x 的最短路径和从 x 到v的最短路径的组合。

标准的全对最短路径算法（例如 Floyd-Warshall 和 Bellman-Ford）是动态规划的典型示例。

动态规划方法的步骤

动态规划算法的设计采用以下四个步骤 -

• 描述最佳解决方案的结构。

• 递归地定义最优解的值。

• 通常以自下而上的方式计算最佳解决方案的值。

• 根据计算的信息构建最佳解决方案。

动态规划 vs. 贪婪 vs. 分而治之

与解决局部优化的贪婪算法相反，动态算法的动机是对问题进行整体优化。

与分治算法不同，动态算法使用较小子问题的输出，然后尝试优化较大的子问题。动态算法使用记忆来记住已解决的子问题的输出。

例子

以下计算机问题可以使用动态规划方法来解决 -

• 斐波那契数列

• 背包问题

• 河内塔

• Floyd-Warshall 和 Bellman Ford 提出的所有对最短路径

• Dijkstra 的最短路径

• 项目调度

• 矩阵链乘法

动态规划既可以采用自上而下的方式，也可以采用自下而上的方式。当然，大多数时候，就 CPU 周期而言，参考先前的解决方案输出比重新计算更便宜。