编辑“︁最优子结构（动态规划）”︁

{{DISPLAYTITLE:最优子结构（动态规划）}}

'''最优子结构'''是[[动态规划]]问题的核心性质之一，指一个问题的最优解包含其子问题的最优解。这一性质使得我们可以通过组合子问题的解来构造原问题的解，从而避免重复计算。

== 定义与原理 ==
若问题满足以下条件，则称其具有'''最优子结构'''：
* 问题可以分解为若干相互重叠的子问题
* 子问题的最优解能组合成原问题的最优解
* 子问题在分解过程中会重复出现

数学表达为：若原问题<math>P</math>的最优解由子问题<math>P_1, P_2, ..., P_k</math>的最优解构成，则存在关系：
<math>OPT(P) = f(OPT(P_1), OPT(P_2), ..., OPT(P_k))</math>
其中<math>OPT</math>表示最优解，<math>f</math>为组合函数。

== 示例分析 ==
=== 经典案例：斐波那契数列 ===
斐波那契数列定义：<math>F(n) = F(n-1) + F(n-2)</math>，其中<math>F(0)=0, F(1)=1</math>

<syntaxhighlight lang="python">
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
</syntaxhighlight>

'''输入/输出示例'''：
* 输入：5
* 输出：5（因为F(5)=5）
* 子问题树：
<mermaid>
graph TD
    F5 --> F4 & F3
    F4 --> F3 & F2
    F3 --> F2 & F1
    F2 --> F1 & F0
</mermaid>

=== 实际应用：钢条切割问题 ===
给定长度为<math>n</math>的钢条和价格表<math>p_i</math>，求最大收益<math>r_n</math>：

递推关系：
<math>r_n = \max_{1 \leq i \leq n}(p_i + r_{n-i})</math>

<syntaxhighlight lang="python">
def cut_rod(p, n):
    if n == 0:
        return 0
    q = -float('inf')
    for i in range(1, n+1):
        q = max(q, p[i] + cut_rod(p, n-i))
    return q
</syntaxhighlight>

'''输入/输出示例'''：
* 输入：p = [0,1,5,8,9,10,17,17,20,24,30], n=4
* 输出：10（切割为2+2时收益最大）

== 识别最优子结构 ==
判断问题是否具有最优子结构的三步骤：
# 验证问题可分解为子问题
# 证明子问题的最优解能构成全局最优解
# 确认子问题相互独立（无后效性）

== 与非最优子结构问题的对比 ==
{| class="wikitable"
|-
! 特征 !! 具有最优子结构 !! 非最优子结构
|-
| 子问题关系 || 可组合成全局解 || 子解无法组合
|-
| 示例 || 最短路径问题 || 最长路径问题
|-
| 动态规划适用性 || 适用 || 不适用
|}

== 常见误区 ==
* '''错误假设'''：认为所有可分解问题都具有最优子结构
* '''反例'''：无权图的最长简单路径问题
* '''关键区别'''：子问题是否相互独立

== 扩展应用 ==
=== 矩阵链乘法 ===
寻找矩阵相乘的最优顺序，使得标量乘法次数最少：
<math>m[i,j] = \min_{i \leq k < j}(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j)</math>

=== 最优二叉搜索树 ===
给定关键字概率分布，构造平均查找时间最短的二叉搜索树：
<math>e[i,j] = \min_{i \leq r \leq j}(e[i,r-1] + e[r+1,j] + w(i,j))</math>

== 总结 ==
最优子结构是动态规划可行性的基础，其核心特征是：
* 问题可分解为重叠子问题
* 局部最优解可构造全局最优解
* 子问题独立无后效

掌握这一概念需要：
# 理解递归分解过程
# 练习经典问题建模
# 识别问题是否适用动态规划

{{编程概念导航}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]