递归

本篇文章是 D瓜哥 读《算法导论》的读书笔记。记录下来是为了方便整理思路，以便啃下“动态规划”这块骨头。 目前侧重记录书中关于“动态规划原理”的介绍。接下来会把书中的例子结合 Java 代码演绎一遍。后续会根据D瓜哥的学习和理解，逐步完善。最终希望达到通过这一篇文章，就能学会、理解动态规划。 山高水远，道阻且长，愿一起努力！ — 2020年01月23日 动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题（在这里，“programming”指的是一种表格法，并非编写计算机程序）。 分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。 动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。 在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子问题。 动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。 动态规划方法通常用来求解最优化问题（optimization problem）。 设计一个动态规划算法的步骤： 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值，通常采用自底向上的方法。 利用计算出的信息构造一个最优解。