0x50 动态规划

通过第0x00章“基本算法”和第0x20章“搜索”的学习，读者应该已经对“问题与状态空间”之间的类比有了更深入的认识。我们提及了递归和递推两种遍历状态空间的基本方法，以及各种降低状态空间规模的手段。对于指数级别等非多项式复杂度的问题，我们介绍了搜索算法，以及提高搜索效率的各种剪枝。本章的主要内容是动态规划算法（DP，Dynamic Programming），它针对满足特定条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。

我们之前探讨过的很多算法都利用问题的可划分性以及子问题之间的相似性来进行归纳，降低求解的复杂度，动态规划也不例外。动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做“无后效性”。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的“状态”，图中的边则对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。

在很多情况下，动态规划用于求解最优化问题。此时，下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。这个条件被称为“最优子结构性质”。当然，这是一种比较片面的说法，它其实告诉我们，动态规划在阶段计算完成时，只会在每个状态上保留与最终解集相关的部分代表信息，这些代表信息应该具有可重复的求解过程，并能够导出后续阶段的代表信息。这样一来，动态规划对状态的抽象和子问题的重叠递进才能够起到优化作用。

“状态”“阶段”和“决策”是构成动态规划算法的三要素，而“子问题重叠性”“无后效性”和“最优子结构性质”是问题能用动态规划求解的三个基本条件。

动态规划算法把相同的计算过程作用于各阶段的同类子问题，就好像把一个固定的公式在格式相同的若干输入数据上运行。因此，我们一般只需要定义出DP的计算过程，就可以编程实现了。这个计算过程就被称为“状态转移方程”。在大多数例题中，

我们讨论状态转移方程的设计思路，并给出最终的方程、边界和目标，而不再讨论程序的实现细节。

$0 \times 51 \sim 0 \times 53$ 节主要侧重最常见的 DP，也就是具有线性阶段划分的 DP 问题。在 $0 \times 51$ 节中，我们先介绍最基本的线性 DP，帮助读者逐步理解动态规划思想，掌握设计 DP 算法基本框架的几条准则。另外，我们在 $0 \times 52$ 节与 $0 \times 53$ 节中会单独讲解背包与区间 DP 这两个重要的部分。我们将探讨背包的各种变形与扩展，在区间 DP 中还会结合讨论“递推”与“记忆化搜索”这两种 DP 基本实现形式。

$0 \times 54 \sim 0 \times 55$ 节把视野扩展到更加一般化的问题。我们将在 $0 \times 54$ 节介绍各种树上的动态规划算法，并在 $0 \times 55$ 节中研究使用 DP 遇到环形、分阶段带环或者具有局部后效性的问题时常见的处理方法。

0x56~0x5B节包括动态规划的各类优化手段。从状态入手，我们有状态压缩、倍增等优化算法。从转移入手，我们可以使用数据结构进行一般的优化，或者挖掘决策单调性，实施单调队列、斜率优化、四边形不等式等比较高级的优化策略。

0x5C~0x5D节与数学内容有所交叉，我们将简单探讨计数类DP和数位统计DP的一些例题，进一步扩充读者的知识储备。

动态规划的艺术在于状态设计和子结构的挖掘。多年来，学界探讨了诸多DP转移的方法和优化手段，然而如何把问题形式化为状态空间，进一步抽象出DP的状态表示和阶段划分，往往是一件考查智力而非套路的事情。本章努力尝试把读者领进大门，但DP的这一难点仍然需要读者自己多加思考。练习设计DP算法并熟练使用它求解问题，也是提升读者在算法竞赛领域思维水平的一个重要途径。