算法导论-DP Apr 15, 2021 · 算法理论 · 分享到: 动态规划 动态规划和分治算法的区别在于，分治算法将问题分成不重叠的几个子问题，分别求解；而动态规划的子问题是重叠的，每次求解子问题后会把子问题保存起来（例如表格），避免了重复计算。 动态规划的四个步骤 刻画一个最优解的结构特征 递归的定义最优解的值 计算最优解的值，通常采用自底向上的方法 利用计算出的信息构造一个最优解 步骤1-3是动态规划的基础，如果我们仅仅需要最优解的值，第四步可以省略。第四步的作用在于维护一个最优解构造信息。 动态规划模式 如果只用正常的递归求解，会反复求一些相同的子问题，造成指数级别的增长。DP有两种等价的实现方法：带备忘的自顶向下法（top-down with memoization）和自底向上法（bottom-up method）。 带备忘的自顶向下法（top-down with memoization） 此方法仍然按照自然的递归形式编写过程，但是过程会保存每个子问题的解（通常保存在一个数组或散列表中）。 当需要一个子问题的解时，过程首先检查是否已经保存过此解， 如果是，则直接返回保存的值，从而节省了计算时间； 否则，按照通常方式计算这个子问题。 自底向上法（bottom-up method） 方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。 因而可以将子问题按规模排序，按由小到大的顺序进行求解。 当求解某个子问题时，所依赖的那些更小的子问题都已经求解完毕，结果已经保存。 每个子问题只求解一次，当求解它时（也是第一次遇到它），所有前提子问题都已经求解完成。 两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归调用开销，自底向上的复杂度函数通常具有更小的系数。 动态规划的两个关键要素 最优子结构，一个问题的最优解包含其子问题的最优解 子问题重叠 某个问题是否适合应用动态规划，它是否具有最优子结构是一个好线索。在DP中，我们通常自底向上的使用最优子结构。同时，DP要求子问题是无关的，同一个原问题的一个子问题的解不影响另一个子问题的解。 适合动态规划的另一个方面是子问题空间必须足够的"小"，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。