动态规划

上一个

测验

下一个

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

大多数情况下，动态规划算法用于解决优化问题。在求解当前子问题之前，动态规划算法会尝试检查之前已求解子问题的结果。子问题的解会被组合起来，以获得最佳的最优最终解。因此，这种范式被称为使用自底向上的方法。

因此我们可以得出结论：

然而，在一个问题中，两个主要属性可以表明该问题可以使用动态规划来求解，它们是：

类似于分治法，动态规划也会组合子问题的解。它主要用于一个子问题的解需要被重复使用的地方。计算出的解会被存储在表格中，这样就不需要重新计算。因此，这种技术适用于存在重叠子问题的地方。

例如，Binary Search 没有重叠子问题。而 Fibonacci 数列的递归程序则有很多重叠子问题。

如果给定问题的最优解可以通过其子问题的最优解获得，则该问题具有最优子结构属性。

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

如果节点 x 位于从源节点 u 到目标节点 v 的最短路径上，那么从 u 到 v 的最短路径是从 u 到 x 的最短路径与从 x 到 v 的最短路径的组合。

标准的 All Pair Shortest Path 算法如 Floyd-Warshall 和 Bellman-Ford 是动态规划的典型示例。

动态规划方法的步骤

动态规划算法使用以下四个步骤设计：

与贪心算法不同，后者关注局部优化，动态规划算法旨在实现问题的整体优化。

与分治算法不同，后者将解组合起来获得整体解，动态规划算法使用较小子问题的输出，然后尝试优化更大的子问题。动态规划算法使用记忆化来记住已求解子问题的输出。

以下计算机问题可以使用动态规划方法求解：

动态规划可以采用自顶向下和自底向上的方式使用。当然，大多数情况下，引用之前解的输出比重新计算在 CPU 周期上更便宜。