动态规划
动态规划方法与分治法类似，分而治之法将问题分解成更小的子问题。但与分而治之法不同的是，这些子问题并非独立解决。相反，这些较小子问题的结果会被记住，并用于解决类似或重叠的子问题。
动态规划算法主要用于解决优化问题。在解决当前子问题之前，动态算法会尝试检查先前已解决子问题的结果。子问题的解会被组合起来，以达到最优的最终解。因此，这种范式被称为自下而上的方法。
因此，我们可以得出结论：−
该问题应该能够分解为更小且相互重叠的子问题。
最终的最优解可以通过对更小子问题进行最优解来实现。
动态算法使用记忆。
然而，在一个问题中，两个主要属性可以表明给定的问题可以使用动态规划来解决。它们是 −
重叠子问题
与分治法类似，动态规划也将子问题的解合并。它主要用于需要重复求解某个子问题的情况。计算出的解存储在表中，这样就无需重新计算。因此，当存在重叠子问题时，需要使用这种技术。
例如，二分查找不存在重叠子问题。而斐波那契数列的递归程序则有许多重叠的子问题。
最优子结构
如果给定问题的最优解可以通过其子问题的最优解获得，则该问题具有最优子结构性质。
例如，最短路径问题具有以下最优子结构性质∠
如果节点 x 位于从源节点 u 到目标节点 v 的最短路径上，则从 u 到 v 的最短路径是从 u 到 x 的最短路径与从 x 到 v 的最短路径的组合。
标准的全对最短路径算法，例如 Floyd-Warshall 和 Bellman-Ford，是动态规划的典型示例。
动态规划方法的步骤
动态规划算法的设计包含以下四个步骤 −
描述最优解的结构。
递归定义最优解的值。
计算最优解的值，通常采用自下而上的方式。
根据计算结果构建最优解。
动态规划、贪婪算法和分治算法
与贪婪算法相比，动态算法致力于对问题进行整体优化，贪婪算法专注于局部优化。
与分治算法相比，动态算法将解组合起来以获得整体解，而分治算法则使用较小子问题的输出，然后尝试优化更大的子问题。动态算法利用记忆来记住已解决子问题的输出。
动态规划示例
以下计算机问题可以使用动态规划方法求解 −
动态规划既可以自上而下使用，也可以自下而上使用。当然，大多数情况下，参考先前的解决方案输出比重新计算更节省 CPU 周期。
