最优子结构

术语：最优子结构

领域：算法/算法设计

定义

最优子结构是动态规划和贪心算法的核心特性，指一个问题的最优解可以由其子问题的最优解递归构造。

形式化定义：设原问题为 $P$，其最优解为 $OPT(P)$。若对于 $P$ 的任意最优解 $OPT(P)$，都可以通过组合其子问题 $P_1,P_2,\dots ,P_k$ 的最优解 $OPT(P_1),OPT(P_2),\dots ,OPT(P_k)$ 来得到，则称 $P$ 满足最优子结构。

跨学科含义

• 在算法设计中：是判断一个问题能否用动态规划求解的必要条件。如果一个问题不具备最优子结构，则无法通过子问题的最优解推导全局最优解
• 在运筹学中：指多阶段决策问题的最优路径，其任意子路径也是对应子问题的最优路径
• 在经济学中：指理性主体的最优决策可以分解为各阶段、各区域的最优决策组合

知识网络

知识图谱分类基于奥苏贝尔同化理论：上位（父级）、下位（子集）、并列、相关

• 父级概念：动态规划 — 最优子结构是动态规划的核心特性
• 下位概念：重叠子问题 — 与最优子结构共同构成动态规划的两大基石
• 相关概念：贪心选择性质, 状态转移方程, 自底向上, 自顶向下

---

判定方法

判断一个问题是否满足最优子结构：

1. 划分子问题：将原问题划分为若干相似子问题
2. 验证推导：检查子问题的最优解能否组合出原问题的最优解
3. 反例验证：尝试构造反例，若存在则不满足

经典示例

问题	满足最优子结构	说明
斐波那契数列	✅	$F(n)=F(n-1)+F(n-2)$
最短路径	✅	最短路径的子路径也是最短的
最长公共子序列	✅	$LCS(X,Y)$ 由子问题推导
旅行商问题	❌	子问题的最优解无法组合成全局最优