形式陈述

动态规划把问题表示为有限状态集合上的递推：每个状态存储一个子问题答案，并按依赖关系自底向上填表，或自顶向下递归并记忆化。优化问题通常需证明最优子结构，例如

$$F(s)={\mathrm{opt}}_{a\in A(s)}\{c(s,a)+F(T(s,a))\},$$

再规定基例与合法状态。其收益来自多个递归分支重复访问相同状态；时间通常是“状态数 × 每状态转移成本”，空间可借依赖宽度压缩。

直觉

不重复解决同一子问题，而把所有可能的“过去摘要”压成状态；一旦状态包含未来决策所需的全部信息，历史细节即可丢弃。

例子与边界

Fibonacci 递归直接展开需指数时间，记忆化后只有 $n$ 个状态。最长公共子序列用前缀长度 $(i,j)$ 作状态，得到 $O(mn)$ 时间。状态太少会丢失信息而使递推错误，状态太多则退化为指数枚举；“有递归式”本身不等于动态规划。

推论与应用

动态规划用于序列比对、背包、最短路、树分解、概率模型和控制。它与分治的区别在于子问题常重叠；与贪心的区别在于保留多个候选状态而非立即作不可逆选择。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Part III, dynamic programming, state recurrences and reconstruction。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 6, dynamic programming and optimal substructure。