如果说有一个算法思想能把顶尖竞赛选手与其他人区分开来，那一定是动态规划：它能把缓慢、重复的暴力枚举转化为高效、有条理的计算。
动态规划（DP）是竞赛编程中的动态规划里最重要、也最让人望而生畏的主题之一。好消息是，DP 并不是什么魔法。一旦学生理解了让它成立的两个条件，以及那些一再出现的少数几种模式，它就会从靠猜的游戏变成一件可靠的工具。本指南将按照我们在竞赛编程课程中的讲法，拆解其核心思想。
动态规划究竟是什么
动态规划是一种解题方法：把一个问题拆分成更小的重叠子问题，每个子问题只求解一次，并把答案存储起来，从而永远不必重新计算。当一个问题具备以下两个性质时，它就很适合用 DP：
- 最优子结构：整个问题的最优答案可以由其子问题的最优答案构建而来。
- 重叠子问题：同样的较小子问题会反复出现，因此缓存它们的结果能节省大量工作。
把它与普通递归对比一下。对斐波那契数列的朴素递归解法会以指数级的次数重复计算相同的值。DP 把每个值只存一次，从而把指数级的工作量压缩为线性级。从重复计算到复用结果的这一转变，正是它的全部要义。
记忆化与递推填表
实现 DP 解法有两种标准方式，二者计算出的答案相同。
自顶向下（记忆化）
你先写出自然的递归解法，然后加上一个缓存。在计算一个子问题之前，先检查它的答案是否已经存储；如果已存储，就立即返回。这种方法很直观，因为它与你口头描述问题的方式一致，而且只会计算你实际需要的那些状态。
自底向上（递推填表）
你先求解最小的子问题，并按顺序填表，逐步构建出完整答案。递推填表避免了递归开销，也便于推导时间和内存，这在比赛限制紧张时尤为重要。优秀的选手两者都会学，并根据问题来选择。
无论选哪种，设计工作都是一样的。先定义状态（表中单个条目的含义），再写出转移（如何由更小的状态计算出某个状态），并设定初始情形。把这三点定好，代码几乎会自己写出来。
反复出现的模式
大多数比赛中的 DP 题都是一小批经典模板的变体。认出模板，问题就解决了一半：
- 0/1 背包：在重量限制下选取一部分物品以最大化价值。
- 最长上升子序列（LIS）：找出按升序排列的最长一段值。
- 最长公共子序列与编辑距离：比较两个序列。
- 硬币找零：统计凑出某个总额的方案数，或求所需硬币的最少数量。
- 区间 DP：在数组的区间上进行优化，例如矩阵链相乘一类的问题。
- 数位 DP 与状压 DP：统计具有特定数位性质的数，或紧凑地跟踪子集。
把这些练到形成本能，就能建立起选手们在时间压力下所依赖的模式识别能力。
DP 在真实比赛中的体现
在 USA Computing Olympiad 中，比赛分为四个组别：Bronze、Silver、Gold 和 Platinum。根据 USACO 官方网站，每位选手都从 Bronze 起步，并通过达到各场比赛而定的晋级分数线获得晋升。动态规划在 Gold 级别及以上成为核心；大多数 Gold 和 Platinum 比赛都至少包含一道 DP 题，而这项技术一直到国际信息学奥林匹克竞赛都不可或缺。比赛形式、计分方式、组别晋级线以及成绩认证规则可能逐年变化，因此请务必在 USACO 官方网站上确认当前的具体细节。
能够晋级的选手，并不是那些背代码的人。他们是那些能看着一道新题，迅速识别出状态与转移的人。
这种能力是可以教会的。通过有结构的练习，一个今天对 DP 望而生畏的学生，几个月内就能从容地设计状态。在 BIAA（标奥），我们一步步培养这种直觉，从最初的递归一直到高级优化。欢迎在我们的博客上探索更多指南，或前往我们的竞赛编程课程页面，了解我们如何指导学生迈向 Gold 乃至更高的层级。