《算法的乐趣》第十一节

本节首先阐述了递归与分治法的关系：分治法产生的子问题与原问题性质相同，只是规模不同，这天然适合用递归实现，通过参数控制规模即可复用同一函数。

本节首先阐述了递归与分治法的关系：分治法产生的子问题与原问题性质相同，只是规模不同，这天然适合用递归实现，通过参数控制规模即可复用同一函数。但分治法并不必须依赖递归，快速傅里叶变换即为非递归实现，快速排序也可用自建栈改写为非递归版本。

接着以Karatsuba大整数乘法为例说明分治法的应用。该算法将两个n位大整数各拆分为高、低两部分，通过三次半规模乘法和若干加减法完成乘积，时间复杂度从O(n²)降至约O(n^1.585)。算法递归地对子问题继续分解，直至1位时直接相乘。

随后引入动态规划。该理论由Bellman于1957年提出，用于多阶段决策优化，其原理是将问题分解为一系列单阶段决策，利用阶段间的递推关系逐段求最优，最终合成整体最优解。书中指出动态规划并非总是多项式时间算法，对NP问题其复杂度仍为指数级，Kleinberg认为它隐含地探查了全部可行解空间，其高效性源于对重叠子问题的剪枝机制。使用动态规划需满足最优化原理（最优子结构）和无后向性（无后效性）两个条件。

最后介绍动态规划的基本思想与设计步骤。与分治法不同，动态规划的子问题相互重叠，需用备忘录避免重复计算。算法设计一般分四步：定义最优子问题（划分决策阶段）、定义状态、定义状态转换方程、确定边界条件。文中以装配站问题、背包问题和最长公共子序列问题为例说明前两步：装配站问题按装配站转移划分阶段，状态为通过某条线某站的最短时间；背包问题若仅以物品编号为状态不满足无后向性，需加入背包容量维度；最长公共子序列问题的状态定义为两个字符串前缀的最长公共子序列长度。