【算法分析与设计】第6篇：动态规划的原理：最优子结构与重叠子问题

上一篇中Kadane算法用O(n)的时间干净利落地解决了最大子数组问题。回顾它的核心递推式dp[i]max(dp[i-1]A[i], A[i])我们会发现一个更深层的结构原问题的最优解可以通过子问题的最优解构造出来。这正是动态规划的理论基石。动态规划不是某一种具体的算法而是一类求解最优化的数学方法。它的英文名“Dynamic Programming”中“Programming”取的是“规划”而非“编程”的语义源于上世纪五十年代Bellman在兰德公司从事运筹学研究时的命名。要准确使用这套方法必须首先理解使它成立的两个前提条件。一、最优子结构定义如果一个问题的最优解包含其子问题的最优解则称该问题具有最优子结构性质。这个定义值得逐字拆解。它不是说“子问题的解可以组合成原问题的解”——这是分治的前提。它说的是原问题的最优解必然由子问题的最优解构成。因此在寻找全局最优时我们无需考虑子问题的次优解因为它们不可能参与构造全局最优。检验最优子结构的一个通用方法是“剪贴法”假设原问题的最优解中某个子问题的解不是最优的那么将该子问题的解替换为更优的那个理应得到一个更优的原问题解。若这个替换与前提矛盾则最优子结构成立。不是所有问题都具备最优子结构。寻找图中的最长简单路径就不具备这一性质——最长路径的子路径未必是子图的最长路径因为最长路径的局部最优与全局最优之间存在冲突。在动态规划建模前这一步的检验绝非可有可无。二、重叠子问题定义若递归算法在求解过程中反复求解相同的子问题而非不断产生全新的子问题则称该问题具有重叠子问题性质。分治算法中子问题通常彼此独立每个子问题只被求解一次。动态规划恰恰相反同一个子问题可能从不同的父问题出发被多次遇到。若不刻意避免递归树中会出现指数规模的重复计算。斐波那契数列的递归求解是重叠子问题的经典反面教材F(n)F(n-1)F(n-2)没有存储中间结果的朴素递归将导致重复计算呈指数增长。动态规划的精髓正是通过有组织的记忆化将每种子问题只计算一次将指数时间压缩到多项式。三、无后效性与状态设计与最优子结构紧密相关的还有一个关键概念——无后效性子问题的解一旦确定就不再受后续更大问题决策的影响即“未来不改变过去”。这一性质直接指导着状态定义这个建模核心环节。状态的定义必须足够丰富使得从该状态出发的未来决策只依赖当前状态的信息而不需要回溯已走过的路径。倘若状态遗漏了必要的上下文未来决策就无法正确做出倘若包含了冗余信息状态空间将不必要地膨胀。状态定义的精确与简约是动态规划建模中最考验功力的地方。四、两种实现范式自顶向下与自底向上动态规划有两种对偶的实现策略。自顶向下备忘录法保持递归调用的结构但用一个数组或哈希表缓存每个子问题的解。每次进入递归前先查表若已有结果则直接返回否则计算并存储。优点是保留了原问题的自然递归结构易于编写和理解仅计算实际用到的子问题。自底向上表格法显式定义子问题的求解顺序从最小规模的子问题开始逐步填充表格直至得到原问题的解。优点是不需要递归调用的栈开销求解顺序明确便于分析复杂度。两种实现在时间复杂度上通常一致选择取决于问题的自然结构和个人偏好。但自底向上的方法对确定求解顺序的要求更高在子问题依赖关系比较复杂时需要额外进行拓扑排序。五、实例展开矩阵链乘法给定n个矩阵的序列A₁,A₂,...,Aₙ目标是找到一种加括号的方式使得计算连乘积所需的标量乘法次数最少。矩阵乘法满足结合律但不同的括号方案开销差异巨大——一个10×100的矩阵乘100×5的矩阵需5000次乘法再乘5×50需2500次总计7500但若先算后两个开销截然不同。状态定义令m[i][j]为计算Aᵢ...Aⱼ所需的最小标量乘法次数。设矩阵Aᵢ的维度为pᵢ₋₁×pᵢ。最优子结构在Aᵢ...Aⱼ的最优加括号方案中必然存在一个最外层划分点ki≤kj使得先算左侧Aᵢ...Aₖ再算右侧Aₖ₊₁...Aⱼ最后将两个结果相乘。两侧子链的计算必须自身最优——这正是最优子结构的体现。由此导出状态转移方程m[i][j]min⁡i≤kj{m[i][k]m[k1][j]pi−1⋅pk⋅pj}m[i][j]i≤kjmin​{m[i][k]m[k1][j]pi−1​⋅pk​⋅pj​}求解顺序矩阵链长度由2增长到n对每个长度枚举起止位置和划分点。三重循环时间复杂度Θ(n³)空间Θ(n²)。这个结构是动态规划的经典范式定义状态、找出转移方程、确定填表顺序。矩阵链乘法看似是纯粹的数学问题但在编译器设计中的寄存器分配、图像处理中的色彩空间转换等场景都有其影子。从下一篇开始我们将进入动态规划最具代表性的实例——01背包问题以及它如何通过精巧的空间优化将一个看似必须二维填表的过程压缩到一维滚动数组。