最优子结构（动态规划）

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

定义与原理[编辑 | 编辑源代码]

若问题满足以下条件，则称其具有最优子结构：

问题可以分解为若干相互重叠的子问题
子问题的最优解能组合成原问题的最优解
子问题在分解过程中会重复出现

数学表达为：若原问题 $P$ 的最优解由子问题 $P_{1}, P_{2}, . . ., P_{k}$ 的最优解构成，则存在关系： $O P T (P) = f (O P T (P_{1}), O P T (P_{2}), . . ., O P T (P_{k}))$ 其中 $O P T$ 表示最优解， $f$ 为组合函数。

示例分析[编辑 | 编辑源代码]

经典案例：斐波那契数列[编辑 | 编辑源代码]

斐波那契数列定义： $F (n) = F (n - 1) + F (n - 2)$ ，其中 $F (0) = 0, F (1) = 1$

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

输入/输出示例：

输入：5
输出：5（因为F(5)=5）
子问题树：

实际应用：钢条切割问题[编辑 | 编辑源代码]

给定长度为 $n$ 的钢条和价格表 $p_{i}$ ，求最大收益 $r_{n}$ ：

递推关系： $r_{n} = \max_{1 \leq i \leq n} (p_{i} + r_{n - i})$

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