526互联

动态规划简介

发布时间 2023-03-29 00:12:49作者: Changry

动态规划与分治法

动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题（在这里，“programming”指的是一种表格法，并非编写计算机程序）。分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做许多不必要的工作，它会反复求解那些公共子子问题，而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

思想和步骤

动态规划方法通常用来求解最优化问题（optimization problem）。这类问题可以有很多可行的解，每个解都有一个值，我们希望寻找具有最优值（最小值或者最大值）的解。我们称这样的解为问题的一个最优解（an optimal solution），而不是（the optimal solution），因为可能有多个解都达到最优值。

我们通常按如下四个步骤来设计一个动态规划算法：

刻画一个最优解的结构特征；
递归地定义最优解的值；
计算最优解的值，通常采用自底向上的方法；
利用计算出的信息构造一个最优解。
步骤 1~3 是动态规划算法求解问题的基础，如果我们仅仅需要一个最优解的值，而非本身，可以忽略步骤 4.

动态规划的思想如下所述：动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需要查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡（time-memory trade-off）的例子。而时间上的节省可能是非常巨大的：可能将一个指数时间的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求解每个子问题，那么动态规划方法的总运行时间就是多项式阶的。

实现方法

动态规划有两种等价的实现方法：
第一种方法称为带备忘的自顶向下法（top-down with memoization）。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表）中。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的（memoized），因为它“记住”了之前已经计算出的结果。

第二种方法称为自底向上法（bottom-up method）。这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因为我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已经求解完成。

两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下的方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上的方法的时间复杂性函数通常具有更小的系数。

子问题图

当思考一个动态规划问题时，我们应该弄清楚所涉及的子问题及子问题之间的依赖关系。问题的子问题图准确地表达了这些信息。它是一个有向图，每个顶点唯一地对应一个子问题。若求子问题 x 的最优解时需要直接用到子问题 y 的最优解，那么在子问题图中就会有一条从子问题 x 的顶点到子问题 y 的顶点的有向边。例如，如果自顶向下过程在求解 x 时需要直接递归调用自身来求解 y，那么子问题图就包含从 x 到 y 的一条有向边。我们可以将子问题图看做自顶向下递归调用树的“简化版”或“收缩版”，因为树中所有对应相同子问题的结点合并为图中的单一顶点，相关的所有边都从父结点指向子结点。

子问题图 G=(V, E) 的规模可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。通常，一个子问题的求解时间与子问题图中对应顶点的度（出射边的数目）称正比，而子问题的数目等于子问题图的顶点数。因此，通常情况下，动态规划算法的运行时间与顶点和边的数量称线性关系。