最优子结构

概述

最优子结构是指一个问题的最优解包含了其子问题的最优解这一性质。它是动态规划和贪心算法共同依赖的核心性质，但两种算法利用该性质的方式截然不同。判断一个问题是否具有最优子结构，是决定能否应用动态规划求解的第一步。

定义

最优子结构（Optimal Substructure）

设问题 $A$ 的一个最优解可以分解为若干子问题 $A_1,A_2,\dots ,A_k$ 的解。如果 $A$ 的最优解中，每个子问题 $A_i$ 的解本身也是子问题 $A_i$ 的最优解，则称问题 $A$ 具有最优子结构性质。

形式化地，设 $c[i,j]$ 为子问题 $(i,j)$ 的最优解的代价，则最优子结构意味着： $c[i,j]=\{\begin{array}{ll}\text{直接计算}& \text{若 }i\ge j\\ \underset{i\le k<j}{\min }\{c[i,k]+c[k+1,j]+\text{合并代价}\}& \text{其他情况}\end{array}$

核心性质

1. 动态规划与贪心算法的共同基础

最优子结构同时是动态规划和贪心算法的必要条件。两者的区别在于：

• 动态规划：先求解所有子问题，再根据子问题的最优解做出选择（先求解后选择）
• 贪心算法：先做出局部最优选择，再求解由此产生的子问题（先选择后求解）

2. 子问题独立性

最优子结构要求子问题之间是独立的——一个子问题的解不影响另一个子问题的解。如果子问题不独立（即存在资源竞争），则不能简单地通过组合子问题的最优解来得到原问题的最优解。

3. 两种刻画方式

• 问题空间：将最优解的组成部分本身视为子问题（如矩阵链乘法中，最优括号化的”左半部分”和”右半部分”）
• 选择空间：将做出选择后剩余的问题视为子问题（如钢条切割中，切下第一段后剩余的部分）

4. 钢条切割中的最优子结构

在 钢条切割 问题中，长度为 $n$ 的钢条的最优切割方案中，第一次切割产生的两段（长度 $i$ 和 $n-i$）各自也必须是最优切割的。否则，我们可以用更优的子方案替换当前子方案，从而得到更好的整体方案——矛盾。

5. 矩阵链乘法中的最优子结构

在 矩阵链乘法 问题中，设 $A_i{A}_{i+1}\cdots A_j$ 的最优括号化在 $A_k$ 和 $A_{k+1}$ 之间分裂，则子链 $A_i\cdots A_k$ 和 $A_{k+1}\cdots A_j$ 的括号化方案也必须是最优的。证明同样采用反证法：若某子链存在更优的括号化方案，替换后可得到更小的总代价——矛盾。

章节扩展

• 14.1 钢条切割 — 钢条切割问题的完整求解过程
• 14.2 矩阵链乘法 — 矩阵链乘法的完整求解过程
• 14.3 动态规划设计要素 — 最优子结构在动态规划设计中的角色
• 动态规划 — 动态规划完整方法论

参见

• 重叠子问题 — 动态规划的另一个核心性质
• 贪心选择性质 — 贪心算法独有的核心性质
• 贪心算法 — 与动态规划的对比
• 替换论证 — 利用最优子结构证明贪心正确性的技术