14.3.5 动态规划法

动态规划常用于明确求最优解的问题。它和分治一样会划分子问题，但关键差别是：动态规划的子问题会重叠，因此要把子问题解保存下来，通过查表避免重复计算。

动态规划的典型特征

特征	说明
最优子结构	原问题最优解可由子问题最优解构造
重叠子问题	不同路径会反复求同一个子问题
状态转移/递推式	用公式描述状态之间的关系
填表	用数组或表保存已求结果

自顶向下与自底向上

课程重点讲了问题规模变化方向。

方式	规模变化	特点
自顶向下	从 $n$ 到 $n-1,n-2...$	若不记忆化，会重复计算，代价很大
自底向上	从 1、2、3 到 $n$	先求小问题并存表，后续直接查表

朴素斐波那契递归会反复求 F(n-1)、F(n-2) 中的重叠子问题；动态规划会把 F(0),F(1),... 依次保存起来。

与分治的区别

对比项	分治	动态规划
子问题	通常独立	大量重叠
结果保存	不强调	必须保存
典型实现	递归分解与合并	表格/数组递推
典型问题	归并排序、二分查找	背包、最长公共子序列

本节例题

单选

动态规划相比分治法最突出的特点是：

A只做当前最优选择B不保存任何中间结果C只适合没有重叠子问题的场景D通过保存子问题结果避免重复计算

自查清单

1. 能否解释什么是重叠子问题？
2. 能否区分自顶向下递归和自底向上填表？
3. 能否说明动态规划为什么常用于最优解问题？