Data Structures Algorithms 简明教程
Dynamic Programming
动态规划方法类似于分而治之，将问题分解为更小且更小的可能子问题。但与分而治之不同，这些子问题不是独立解决的。相反，这些较小子问题的结果会被记住并用于解决相似的或重叠的子问题。
通常，动态规划算法用于解决优化问题。在解决手头的子问题之前，动态算法将尝试检查以前已解决的子问题的结果。子问题的解会结合在一起以便获得最佳的最终解。因此，这种范式被称为使用自底向上的方法。
所以我们可以得出以下结论：
-
该问题应该能够被分成较小的重叠子问题。
-
可以通过使用较小子问题的最优解来获得最终的最优解。
-
Dynamic algorithms use memorization.
然而，在一个问题中，两个主要属性可以表明给定问题可以使用动态规划来解决。它们是：
Overlapping Sub-Problems
与分而治之的方法类似，动态规划也结合了子问题的解。它主要用于重复需要一个子问题的解的情况。已计算的解会存储在一个表中，这样无需重新计算它们。因此，当存在重叠子问题时就需要这种技术。
例如，二分查找没有重叠子问题。然而，斐波那契数的递归程序有许多重叠子问题。
Optimal Sub-Structure
如果给定问题的最优解可以使用其子问题的最优解获得，则给定问题具有最优子结构属性。
例如，最短路径问题具有以下最优子结构属性：
如果一个节点 x 位于从源节点 u 到目标节点 v 的最短路径中，则从 u 到 v 的最短路径是从 u 到 x 的最短路径和从 x 到 v 的最短路径的组合。
标准的全对最短路径算法，如 Floyd-Warshall 和 Bellman-Ford，是动态规划的典型示例。
Steps of Dynamic Programming Approach
动态规划算法是使用以下四个步骤设计的：
-
描述最优解的结构。
-
递归定义最优解的值。
-
计算最优解的值，通常采用自底向上的方式。
-
从已计算的信息中构建一个最优解。
Dynamic Programming vs. Greedy vs. Divide and Conquer
与贪心算法（着重于局部优化）不同，动态算法的目的是对问题进行整体优化。
与分治算法（将解组合在一起以达到最终解）不同，动态算法使用子问题的结果，然后尝试优化更大的子问题。动态算法利用记忆化来记住已解决子问题的输出。