算法

动态规划入门

Tip 本篇文章是 D瓜哥 读《算法导论》的读书笔记。记录下来是为了方便整理思路,以便啃下“动态规划”这块骨头。 目前侧重记录书中关于“动态规划原理”的介绍。接下来会把书中的例子结合 Java 代码演绎一遍。后续会根据D瓜哥的学习和理解,逐步完善。最终希望达到通过这一篇文章,就能学会、理解动态规划。 山高水远,道阻且长,愿一起努力!  — 2020年01月23日 动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题(在这里,“programming”指的是一种表格法,并非编写计算机程序)。 分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。 动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。 在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子问题。 动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了不必要的计算工作。 动态规划方法通常用来求解最优化问题(optimization problem)。 设计一个动态规划算法的步骤: 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值,通常采用自底向上的方法。 利用计算出的信息构造一个最优解。 算法原理 适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。 最优子结构 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。因此,某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个好线索。 发掘最优子结构性质的通过模式 证明问题最优解的第一个组成部分是做出一个选择。做出这次选择会产生一个或多个待解的子问题。 对于一个给定问题,在其可能的第一步选择中,你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择。 给定可获得最优解的选择后,你确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间。 利用“剪切-粘贴”(cut-and-paste)技术证明:作为构造原问题最优解的组成部分,每个子问题的解就是它本身的最优解。证明这一点是利用反证法:假定子问题的解不是其自身的最优解,那么我们就可以从原问题的解中“剪切”掉这些非最优解,将最优解“粘贴”进去,从而得到原问题一个更优的解,这与最初的解是原问题最优解的前提假设锚段。