动态规划：从贝尔曼的智慧到算法竞赛的基石

引言在算法设计的广阔天地中动态规划Dynamic Programming简称DP无疑是一颗璀璨的明星。它既不像二分查找那样简洁直接也不似深度优先搜索那样易于直觉理解而是以一种近乎“魔法”的方式将复杂问题拆解为相互关联的子问题通过缓存中间结果来避免重复计算最终高效地求得最优解。对于初学者而言动态规划常常令人望而生畏——状态如何定义转移方程如何推导这些问题似乎没有一个固定的模板可以套用。然而正如我们将在这篇文章中看到的动态规划并非遥不可及的高深理论。通过系统地理解其核心思想并通过大量经典题目的练习每一个学习者都可以掌握这一强大的工具。本文将从动态规划的发明故事讲起追溯其发展历程然后以洛谷上的一系列经典题目为载体按照不同的题型分类讲解动态规划的核心技巧。最后我们将探讨动态规划在算法竞赛中的演进方向以及它所引申出的各类优化方法和跨领域应用。无论你是刚开始接触DP的初学者还是希望系统梳理知识体系的进阶选手相信都能从这篇文章中有所收获。第一篇动态规划的诞生——贝尔曼的智慧1.1 从多阶段决策到“动态规划”动态规划的起源可以追溯到20世纪50年代初。当时美国数学家理查德·贝尔曼Richard Bellman在研究多阶段决策过程的优化问题时逐渐发现了这类问题背后的结构特征。1949年夏天贝尔曼在斯坦福大学数学系担任终身副教授同时作为顾问在圣塔莫尼卡的兰德公司RAND Corporation工作。正是在这一时期他对多阶段决策问题产生了浓厚的兴趣。贝尔曼此前已经在纯数学和解决物理世界中的应用问题方面展现出了杰出的能力但他选择转向后来被称为运筹学的应用数学领域。在那个年代应用实践者被视为数学领域的“二等公民”但贝尔曼坚信现实世界中的挑战更需要数学的力量他以饱满的热情投身于这一新兴领域。在研究过程中贝尔曼提出了著名的最优化原理Principle of Optimality该原理指出无论初始状态和初始决策如何后续的决策都必须构成一个相对于由初始决策导致的状态的最优策略。这一看似简单的原理实际上是动态规划的理论基石——它告诉我们一个问题的最优解可以通过其子问题的最优解来构造。1.2 “动态规划”命名的轶事关于“动态规划”Dynamic Programming这个名称的由来有一个广为流传的故事。1950年贝尔曼在兰德公司工作期间提出了这一方法并为其命名。然而他选择“programming”这个词并非指计算机编程而是取“计划”或“制定最优行动方案”之意。有趣的是贝尔曼之所以选择这个名称还有一层特殊的考虑。当时他受到美国国防部长查尔斯·威尔逊Charles Wilson的影响——威尔逊对“研究”这个词颇有偏见认为它带有某种“学术化”的色彩。为了避免引起不必要的政治争议贝尔曼特意选用了“规划”这个听起来更务实、更工程化的术语来描述他的方法。这一巧妙的命名策略使得动态规划能够顺利地在政府部门的研究项目中被采用和推广。1.3 核心原理的数学表述从最优化原理出发贝尔曼推导出了该方法的递推关系——贝尔曼方程Bellman Equation。该方程将一个阶段的状态价值与后续状态的价值联系起来是动态规划求解过程的数学表达。从那时起动态规划逐渐从运筹学的一个分支发展成为计算机科学中最重要的算法设计范式之一。1957年贝尔曼出版了名著《Dynamic Programming》系统地阐述了动态规划的理论和方法。1961年和1962年他相继再版此书进一步阐明了动态规划的理论框架。1966年动态规划登上国际顶级期刊《Science》贝尔曼作为唯一作者发表了相关论文该论文至今已被引用超过两万八千次。为纪念贝尔曼的贡献动态规划的核心方程被命名为贝尔曼方程。1.4 动态规划进入信息学竞赛动态规划从运筹学的学术领域走向算法竞赛的舞台经历了约四十年的沉淀。1994年国际信息学奥林匹克竞赛IOI首次出现了动态规划题目——那就是后来成为经典的《数字三角形》Number Triangles。这道题要求从数字金字塔的顶部出发每一步向左下或右下移动求到底部的最大路径和。它的出现第一次将“动态规划”这个名词刻进了信息学竞赛的历史。在国内动态规划首次出现在1995年的全国青少年信息学奥林匹克竞赛NOI中题目是《石子归并》。从此之后动态规划一发而不可收成为了近年来NOIP、NOI以及IOI必考的内容之一也是算法竞赛中最具挑战性和区分度的题型之一。动态规划之所以能在算法竞赛中占据如此重要的地位根本原因在于它完美地平衡了“效率”与“精确性”——相比贪心算法它能够保证全局最优解相比暴力搜索它通过状态缓存极大地降低了时间复杂度。正如我们将在这篇文章中看到的掌握动态规划的核心思想对于每一位算法竞赛选手而言都是至关重要的。第二篇动态规划的基石——核心概念与方法论在深入讲解具体题目之前我们有必要先梳理一下动态规划的几个核心概念。理解这些概念是能够独立设计动态规划算法的前提。2.1 最优子结构最优子结构是指一个问题的最优解包含其子问题的最优解。换言之我们可以通过求解子问题的最优解来构造原问题的最优解。这是动态规划能够应用的根本前提。以经典的“纸币问题”为例要凑出金额w的最少纸币数如果最后一枚纸币面额为a[i]那么凑出w-a[i]的最少纸币数一定也是最优的。否则如果我们能找到一个更优的凑出w-a[i]的方案那么把它和a[i]组合起来就能得到一个比原方案更好的凑出w的方案——这就产生了矛盾。正是这种性质使得我们可以从较小的子问题逐步递推到较大的问题。2.2 重叠子问题重叠子问题是指在对原问题进行递归求解时会反复遇到相同的子问题。动态规划通过保存已解决子问题的解即“记忆化”或“制表法”来避免重复计算从而显著提高效率。以斐波那契数列为例F(5) F(4) F(3)而F(4) F(3) F(2)。在这里F(3)被重复计算了多次。如果不加优化直接递归求解的时间复杂度将达到O(2^n)而如果我们用一个数组保存每个F(i)的值则只需要O(n)的时间即可完成计算。这正是动态规划的核心优势所在。2.3 无后效性无后效性是指一旦某个阶段的状态被确定该阶段之后的过程演变就不再受之前阶段决策的影响。换句话说状态本身已经包含了所有影响未来决策的必要信息。无后效性确保了我们可以按阶段顺序处理问题而不必回溯到更早的状态。例如在“数字三角形”问题中到达第i行第j列的最大路径和只依赖于上一行到达该位置的两个可能来源而不会受到更早的路径选择影响。这正是动态规划能够“递推”而非“回溯”的原因。2.4 状态与状态转移方程状态是动态规划中最核心的概念。一个状态通常用一个或多个变量来描述问题在某个阶段的状况。状态转移方程则描述了状态之间的递推关系它定义了如何从较小的状态推导出较大的状态。设计状态和状态转移方程是动态规划解题的关键步骤也是最考验分析能力的地方。好的状态定义应当简洁明了能够准确地描述问题同时又要避免冗余——状态越多时间和空间开销就越大。正如我们在后面的题目讲解中将会反复看到的不同的状态定义方式可能导致截然不同的解题难度和效率。2.5 阶段与决策在动态规划中通常按照某种顺序将问题划分为若干个阶段如时间顺序、空间顺序、物品顺序等。在每个阶段我们需要做出决策——即选择下一步的行动方案。决策会导致状态的变化从而进入下一个阶段。例如在背包问题中阶段就是逐个考虑每个物品决策就是“选”或“不选”这个物品在数字三角形中阶段是金字塔的行数决策是从上一行的哪个位置走过来。清晰地识别阶段和决策是设计动态规划算法的第一步。第三篇题型分类精讲——从入门到进阶本章将以洛谷上的18道经典动态规划题目为载体按照题目类型分类讲解。我们将从最简单的基础DP开始逐步深入到背包问题、线性DP、树形DP等进阶内容。每道题都会分析状态定义、转移方程和解题要点。3.1 基础DP入门基础DP题目通常具有明显的阶段划分特征状态定义直观转移方程简单是初学者理解动态规划思想的最佳切入点。【P2842】纸币问题 1——最少纸币数完全背包最值题目描述有n种面额互不相同的纸币每种纸币有无限张。要凑出金额w问最少需要多少张纸币。解题思路这是一道典型的完全背包最值问题。定义dp[i]表示凑出金额i所需的最少纸币张数。对于每个金额i尝试使用每一种纸币a[j]面额如果i ≥ a[j]那么使用这张纸币后剩余金额为i-a[j]所需纸币数为dp[i-a[j]]1。在所有可能的纸币选择中取最小值即可。状态转移方程为textdp[i] min(dp[i - a[1]], dp[i - a[2]], ..., dp[i - a[n]]) 1其中dp[0] 0凑出0元不需要任何纸币。解题要点初始化dp[0] 0其余dp[i]初始化为一个很大的数如INF。递推方向从小到大枚举金额i从1到w。时间复杂度O(n × w)对于n ≤ 1000、w ≤ 10⁴的数据范围完全可行。这道题的关键在于理解“子问题最优解”的思想凑出w的最优方案一定是由凑出某个w-a[j]的最优方案加上一张a[j]的纸币构成的。【P2840】纸币问题 2——支付方案数顺序相关的计数题目描述有n种面额互不相同的纸币每种有无限张。支付金额w求有多少种支付方式。注意同样的纸币组合如果支付顺序不同会被视作不同的方式。解题思路定义dp[i]表示凑出金额i的方案数。由于顺序不同算作不同方案我们不需要考虑组合的“去重”问题只需要在每种金额i下依次尝试所有纸币面额即可。状态转移方程为textdp[i] Σ dp[i - a[j]] 对所有满足a[j] ≤ i的j边界条件dp[0] 1金额0只有一种方案——不支付任何纸币。解题要点初始化dp[0] 1。递推顺序外层循环遍历金额i从1到w内层遍历所有纸币面额。这样做会考虑所有可能的支付顺序。取模题目要求答案对10⁹7取模在递推过程中及时取模。示例演算纸币面额[1,2,5]目标金额5dp[1] 1仅用1元硬币dp[2] 211或2dp[3] 3111,12,21dp[5] 8包含5元硬币在内的所有组合【P2834】纸币问题 3——组合方案数顺序无关的计数题目描述与P2840相同的数据范围但同样的纸币组合如果支付顺序不同被视为同一种方式。问有多少种方式支付金额w。解题思路这是典型的组合计数问题需要使用“按物品阶段递推”的方法以避免重复计数。定义f[i][j]表示只使用前i种纸币凑出金额j的方案数。状态转移有两种情况不使用第i种纸币方案数为f[i-1][j]使用第i种纸币先使用一张第i种纸币剩余金额为j-a[i]方案数为f[i][j-a[i]]注意这里使用的是f[i]而不是f[i-1]因为同一物品可以无限使用这是完全背包组合计数的关键因此转移方程为textf[i][j] f[i-1][j] f[i][j-a[i]] 当j ≥ a[i]时 f[i][j] f[i-1][j] 当j a[i]时边界条件f[i][0] 1金额0只有一种方案不使用任何纸币。空间优化观察发现f[i]只依赖于f[i-1]和f[i]本身因此可以将第一维去掉使用一维数组滚动更新cppf[0] 1; for (int i 1; i n; i) { for (int j a[i]; j w; j) { f[j] (f[j] f[j - a[i]]) % mod; } }注意内层循环需要从小到大枚举j而不是从大到小这是因为我们允许无限使用同一种物品。三道纸币问题的对比题目类型递推顺序注意事项P2842完全背包最小值金额内层物品内层取最小值P2840完全背包计数顺序相关金额外层物品内层顺序相关不判重P2834完全背包计数顺序无关物品外层金额内层需从小到大枚举判重【P1216】数字三角形——路径最大和题目描述给定一个数字金字塔从顶部出发每次可以走到左下方或右下方求从顶部到底部的路径最大和。解题思路这是动态规划进入信息学竞赛的第一道题目也是初学者学习DP的最佳入门题。定义dp[i][j]表示从顶部到达第i行第j列的最大路径和。由于每一步只能从左上方或右上方走来因此状态转移方程为textdp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]其中a[i][j]是第i行第j列的数字。边界条件第1行第1列的dp[1][1] a[1][1]第1列只能由正上方转移来第i行第i列只能由左上方转移来。解题要点递推方向从上到下逐行计算。最终答案max(dp[n][j])即最后一行中的最大值。记忆化搜索替代方案也可以从底部向上递推这样最终答案就是dp[1][1]。数字三角形问题的本质是“最优子结构”的直观体现到达某一位置的最优路径必然是由到达其上方位置的最优路径延伸而来的。3.2 背包问题背包问题是动态规划中最经典、最重要的题型之一。它模拟了在有限容量下选择物品以最大化价值的问题变体众多。【P1048】采药——01背包题目描述辰辰在限定时间T内采药每种草药只能采一次每种草药有采集时间t[i]和价值v[i]。求在不超过时间T的前提下能获得的最大价值。解题思路这是01背包的标准模板题。定义dp[j]表示在时间j内能获得的最大价值。对于每株草药决策是“采”或“不采”。状态转移方程一维优化版textfor i 1 to n: for j T down to t[i]: dp[j] max(dp[j], dp[j - t[i]] v[i])为什么内层循环要逆序因为01背包中每种物品只能选一次。如果正序遍历j那么在更新dp[j]时可能会重复使用同一个物品多次——因为dp[j-t[i]]可能已经在同一轮循环中被更新过了。逆序遍历可以确保每个物品只被考虑一次。解题要点初始化dp[0] 0其余dp[j]初始化为0。最终答案max(dp[j])即所有容量下的最大值。时间复杂度O(n × T)。【P1049】装箱问题——01背包变形求最小剩余空间题目描述有一个箱子容量为V有n个物品每个物品有体积。任取若干个装入箱子使箱子剩余空间最小输出最小剩余空间。解题思路将物品的体积视为“价值”目标是让装入物品的总体积尽可能大接近V。这样问题就转化为了01背包在容量V的限制下求能装入的最大总体积。最终答案为V - max_volume。状态转移方程textdp[j] max(dp[j], dp[j - w[i]] w[i])其中dp[j]表示容量为j的箱子能装下的最大体积。解题要点装箱问题本质上是01背包的一个简单变形只需将物品的重量和价值视为同一个量即可。最终答案 V - dp[V]。【P1616】疯狂的采药——完全背包题目描述与P1048采药类似但每种草药可以无限次采集每种草药数量无限。求在限定时间T内能获得的最大价值。解题思路完全背包问题每种物品可以取无限次。只需要将01背包内层循环的逆序遍历改为正序遍历即可。状态转移方程textfor i 1 to n: for j t[i] to T: dp[j] max(dp[j], dp[j - t[i]] v[i])为什么正序遍历可以实现无限取当j从小到大遍历时dp[j - t[i]]可能在本轮循环中已经被更新过这意味着同一物品可以被多次使用。这正是完全背包的核心特征。解题要点完全背包的空间优化版本与01背包的唯一区别就是内层循环的顺序。时间复杂度仍为O(n × T)但由于物品数量无限n通常可以取到较大值。可进行优化若两件物品i和j满足t[i] ≤ t[j]且v[i] ≥ v[j]则物品j可以被直接忽略。【P1802】5倍经验日——01背包变形必选且分输赢题目描述有n个对手每个对手可以选择打或不打。如果打需要消耗use[i]瓶药如果药不够即药量少于use[i]则只能选择不打。打输获得lose[i]经验打赢获得win[i]经验。求在有限药量下能获得的最大经验。解题思路这是一个01背包的变形——每个对手“打”对应一个决策但“打”的结果又有两种输或赢同时“不打”也有固定收益。定义dp[j]表示在药量为j时能获得的最大经验。对于第i个对手有两种选择不打获得lose[i]经验药量不变。打消耗use[i]瓶药获得win[i]经验前提是j ≥ use[i]。状态转移方程为textdp[j] max(dp[j] lose[i], dp[j - use[i]] win[i]) 当j ≥ use[i]时 dp[j] dp[j] lose[i] 当j use[i]时优化技巧也可以先假设全部失败将lose[i]加入基础经验然后将win[i] - lose[i]作为“额外收益”进行01背包。解题要点这道题与普通01背包的不同之处在于即使不选物品也有收益lose[i]。因此基础经验需要单独累计。最终答案 基础经验 通过背包选择获得的最大额外收益。【P1064】金明的预算方案——依赖背包有依赖的背包问题题目描述有n个物品分为主件和附件。每个附件必须依附于其主件才能购买且每个主件最多有2个附件。给定总预算求在预算内能获得的最大总价值价值 价格 × 重要度。解题思路这是“有依赖的背包问题”的经典代表。由于每个主件的附件数量很少最多2个我们可以将每个主件和它的附件看作一个组合然后枚举这个组合的所有可行购买方案。对于每个主件可能的购买方案有只买主件买主件附件1买主件附件2买主件附件1附件2如果存在两个附件将这些方案视为一个分组背包中的一组在每组中最多选择一种方案然后按照分组背包的方法求解。解题要点先读入数据识别主件和附件的关系将附件挂在对应的主件下。对每个主件计算上述4种方案的价格和价值。使用分组背包DP外层循环遍历每个主件内层从总预算向下遍历再内层遍历该主件的4种方案。注意附件不能独立购买必须随主件一起购买。这道题是依赖背包问题的入门题目为后续学习树形依赖背包如“有依赖的背包问题”中的森林形依赖奠定了基础。【P1077】摆花——多重背包计数题目描述有n种花第i种花最多有a[i]盆需要摆出恰好m盆花且同种花必须摆在一起即按种类顺序摆放。求摆花方案数。解题思路这是一个多重背包计数问题。定义dp[i][j]表示只考虑前i种花总共摆出j盆的方案数。对于第i种花我们可以摆0盆、1盆、……、a[i]盆。状态转移方程为textdp[i][j] Σ dp[i-1][j - k] 0 ≤ k ≤ a[i] 且 j - k ≥ 0边界条件dp[0][0] 1。空间优化由于dp[i]只依赖于dp[i-1]可以优化为一维数组。但注意内层循环需要从后往前遍历相当于多重背包的逆序处理。解题要点多重背包计数与完全背包计数的区别在于每种物品有数量上限。本题中花必须按顺序摆放因此“同种花摆在一起”的条件已经自动满足——我们按种类顺序递推自然保证了摆放的顺序性。当a[i]很大时可以使用前缀和优化或单调队列优化将转移复杂度从O(m²)降至O(m)。3.3 线性DP线性DP是指状态定义中维度与输入规模呈线性关系、状态转移沿线性方向进行的DP类型。这类问题的特点是阶段划分清晰通常可以一维递推。【P1115】最大子段和题目描述给定一个整数序列可能包含负数求一段连续且非空的子序列的最大和。解题思路这是线性DP中最经典的题目之一。定义dp[i]表示以第i个元素结尾的最大子段和。状态转移方程为textdp[i] max(a[i], dp[i-1] a[i])解释以第i个元素结尾的最大子段和要么就是a[i]本身前面的累加和为负不如从头开始要么是前面的最优解加上a[i]前面的累加和为正继续累加有利可图。解题要点最终答案max(dp[i])。时间复杂度O(n)空间复杂度可优化至O(1)——因为dp[i]只依赖于dp[i-1]。贪心解法的区别贪心只考虑局部最优而动态规划通过状态累积实现了全局统筹。【P2196】挖地雷——带路径记录的线性DP题目描述有N个地窖N ≤ 20每个地窖有一定数量的地雷。给出地窖之间的连通路径单向只能从小号地窖走向大号地窖。某人可以从任一地窖出发每次移动到编号更大且联通的节点求能挖到的最多地雷数并输出路径。解题思路定义dp[i]表示以第i个地窖为终点的最多地雷数。状态转移方程textdp[i] max(dp[j] a[i]) 对所有能从j到达i的j同时需要用pre[i]记录在最优方案中i的前驱节点以便最后输出路径。解题要点由于只能从小号走向大号我们可以按照编号从小到大或从大到小的顺序进行DP。路径记录是本题的难点在更新dp[i]时如果dp[j] a[i] dp[i]则更新dp[i]的同时记录pre[i] j。最终答案max(dp[i])然后从对应节点开始沿着pre数组回溯输出路径。【P3842】线段——二维状态DP题目描述在一个n×n的平面上第i行有一条线段左端点为(i, L[i])右端点为(i, R[i])。从(1,1)出发要求沿途走过每一行的整条线段最终到达(n, n)求最短路径长度。解题思路这是典型的按行递推的DP问题。由于每行走完线段后必须停在左端点或右端点才能向下行走我们可以定义两个状态f[i][0]走完第i行的线段后停在左端点L[i]的最短路径长度。f[i][1]走完第i行的线段后停在右端点R[i]的最短路径长度。状态转移需要考虑四种情况从上一行的左/右端点出发走到本行的左/右端点并在本行走完整条线段。解题要点本行内走线段的距离是固定的|R[i] - L[i]|。从上一行的某端点走到本行的某端点需要计算曼哈顿距离。本题巧妙之处在于利用了“每行线段必须全部走过”这一条件将状态简化到仅需记录停靠端点即可。【P2392】kkksc03考前临时抱佛脚——任务分配01背包题目描述kkksc03有四门科目每门科目有若干道题目每道题需要一定时间。他可以同时使用左脑和右脑思考但一道题只能被一个脑处理。求完成所有科目的最少总时间。解题思路由于四门科目相互独立可以分别计算每门科目的最小耗时然后求和。对于一门科目有s道题目每道题耗时t[i]。我们需要将这些题目分配到左脑和右脑中使两脑耗时之差最小。这等价于在不超过总耗时一半的前提下让其中一脑的耗时尽可能接近总耗时的一半——这正是01背包问题。定义dp[j]表示能否用若干道题凑出总耗时j。遍历所有题目更新dp数组。然后找到最大的不超过sum/2的可凑出的时间则该门科目的最小耗时 max(该时间, sum - 该时间) sum - 该时间因为该时间已经是不超过一半的最大值另一半自然是不小于一半的最小值。解题要点四门科目独立计算最后求和。01背包中dp数组用bool类型或bitset优化。注意边界sum为0时dp[0] true。3.4 网格DP网格DP是在二维网格上进行的动态规划通常用于求解路径计数、最大小路径和等问题。【P1002】过河卒——带障碍的路径计数题目描述棋盘上A点有一个过河卒需要走到B点。卒可以向下或向右移动。棋盘上C点有一个马马所在点和所有一步可达的点共9个位置为控制点卒不能经过控制点。求从A到B的合法路径总数。解题思路定义dp[i][j]表示从A(0,0)走到(i,j)的路径数。卒只能从上方或左方走来因此状态转移方程为textdp[i][j] dp[i-1][j] dp[i][j-1] 当(i,j)不是控制点解题要点预处理马的控制点标记为不可达。边界条件dp[0][0] 1。注意处理边界第一行只能从左方转移来第一列只能从上方转移来。当n和m较大时n,m ≤ 20直接递推即可。3.5 树形DP与图论DP树形DP是指在树形结构上进行的动态规划通常使用DFS或拓扑排序来实现状态转移。这类问题往往需要先处理子树再向上递推。【P1434】滑雪——记忆化搜索题目描述在一个R×C的矩阵中每个格子有高度。Michael可以从任一点开始滑雪每次只能滑向相邻的四个方向且高度必须降低。求最长的滑坡长度。解题思路由于不知道起点在哪不能直接按顺序DP。但我们可以使用记忆化搜索定义dp[i][j]表示从(i,j)出发的最长滑坡长度。递归搜索时如果某个邻居高度更低则尝试从邻居继续下滑并取所有方向的最大值加1。由于每个格子的结果在计算后会被保存当再次访问时直接返回避免了重复计算。状态转移方程textdp[i][j] max(dp[邻居]) 1 对所有高度更低的邻居解题要点记忆化搜索本质上是递归实现的动态规划通过“缓存”中间结果避免重复搜索。时间复杂度O(R × C)每个格子只计算一次。本题也可以用递推实现——按高度排序后递推但记忆化搜索更为直观。【P4017】最大食物链计数——拓扑排序DP题目描述给定一个食物网有向图生产者入度为0到顶级消费者出度为0的路径称为最大食物链。求所有最大食物链的数量取模80112002。解题思路这是图论中“有向无环图路径计数”的典型问题。由于食物网是一个DAG我们可以使用拓扑排序来确定递推顺序。定义dp[i]表示从某个生产者到i的路径数。按照拓扑序遍历节点对于每条边u → vtextdp[v] (dp[v] dp[u]) % mod初始化所有生产者的dp值为1。最终答案所有出度为0的节点的dp值之和。解题要点使用拓扑排序保证递推顺序正确——只有所有前驱节点都处理完后才能处理当前节点。注意取模运算。也可以用记忆化搜索从每个生产者出发但效率不如拓扑排序。第四篇动态规划的演进——从经典优化到跨领域融合动态规划诞生至今已有七十余年其理论体系和应用范围仍在不断扩展。本章将介绍动态规划在算法竞赛中的优化技术演进以及它如何与其他领域融合衍生出更强大的算法范式。4.1 DP优化方法概览随着问题规模的增大和复杂度的提升朴素的动态规划往往难以满足时间要求。算法竞赛选手和研究人员发展出了多种DP优化技术将原本无法处理的规模变得可行。4.1.1 状态设计优化最基本的优化是对状态本身进行精简。如果状态能从三维降到两维甚至一维将对时间复杂度和常数产生巨大影响。例如在背包问题中二维DP可以优化为一维滚动数组在纸币问题3中通过观察发现当前状态只依赖于上一阶段的状态从而节省了空间。4.1.2 单调队列优化当状态转移方程形如dp[i] min/max(dp[j] val(i, j))且val(i, j)可以分解为与i、j分别相关的部分时可以使用单调队列维护一个滑动窗口中的最值将O(n²)的时间复杂度降为O(n)。具体来说如果转移只依赖于上一状态的某个连续段的最值且相邻状态的区间左右端点单调不降就可以用单调队列来优化。单调队列优化常用于解决区间DP和某些线性DP问题。4.1.3 斜率优化当转移方程可以转化为dp[i] min(dp[j] (s[i] - s[j])² C)这种形式时就可以使用斜率优化。将方程改写为dp[i] min(dp[j] s[j]² - 2·s[i]·s[j]) s[i]² C其中dp[j] s[j]²是y2·s[j]是xs[i]是斜率。问题转化为在平面上找一条斜率为k的直线经过某个点使得截距最小。通过维护一个凸包下凸包用于求最小值上凸包用于求最大值可以在O(n)或O(n log n)时间内完成转移将O(n²)优化到O(n)。4.1.4 四边形不等式优化当状态转移方程形如dp[i][j] min(dp[i][k] dp[k1][j] w[i][j])区间DP时如果w[i][j]满足四边形不等式那么决策点具有单调性可以使用四边形不等式优化将O(n³)的时间复杂度降为O(n²)。四边形不等式定义为textw[i][j] w[i][j] ≤ w[i][j] w[i][j] 对于任意 i ≤ i ≤ j ≤ j如果w满足这个性质那么可以证明决策点s[i][j]即使dp[i][j]取最小值的k满足texts[i][j-1] ≤ s[i][j] ≤ s[i1][j]利用这一性质可以大幅缩小枚举k的范围。4.1.5 状态压缩DP当状态的维度较多但每个维度的取值范围很小通常为2种状态时可以用二进制位来表示状态将多维状态压缩为一个整数。这种方法称为状态压缩DP。状态压缩DP常用于解决棋盘覆盖、旅行商问题TSP等NP难问题的小规模求解。例如用M位的二进制数表示一行的状态0表示空格1表示被覆盖然后在行之间进行转移。状态压缩DP的时间复杂度通常是O(n × 2^M × 2^M)在M较小时如M ≤ 20可行。4.1.6 动态DPDDP动态DP是一种用于解决带修改的动态规划问题的技术。其核心思想是用矩阵来描述状态转移方程然后用线段树等数据结构维护区间转移矩阵的乘积从而支持单点修改和区间查询。例如斐波那契数列的递推关系可以用2×2矩阵表示。当数列的某些项需要修改时动态DP可以在O(log n)时间内完成更新而重新计算整个DP表需要O(n)时间。动态DP的局限性在于它对转移方程的要求较高——需要能够用矩阵乘法或满足结合律的广义运算来描述。但对于满足条件的问题动态DP提供了一种优雅而高效的解决方案。4.2 从DP到强化学习动态规划与强化学习Reinforcement Learning有着深厚的渊源。事实上强化学习中的核心算法——策略迭代和价值迭代——正是动态规划在马尔可夫决策过程MDP中的应用。在强化学习中智能体需要在未知环境中通过试错学习最优策略。当环境模型已知时可以使用动态规划来求解最优策略。贝尔曼方程在强化学习中扮演着核心角色——它定义了状态价值函数与后继状态之间的递归关系textV(s) max_a [R(s,a) γ·Σ P(s|s,a)·V(s)]这正是动态规划最优化原理在随机决策过程中的推广。通过反复迭代这个贝尔曼方程即价值迭代可以收敛到最优状态价值函数进而得到最优策略。然而传统的动态规划在强化学习中的应用面临着“维数灾”问题——当状态空间很大时如围棋有约10¹⁷⁰种状态精确求解贝尔曼方程在计算上是不可能的。4.3 近似动态规划ADP与神经网络为了克服维数灾研究人员发展了近似动态规划Approximate Dynamic ProgrammingADP又称自适应动态规划。ADP利用函数近似结构如神经网络来逼近动态规划方程中的性能指标函数和控制策略使之满足贝尔曼最优性原理从而获得近似最优解。ADP由美国学者Paul J. Werbos于1977年首次提出它融合了强化学习和动态规划的思想模拟人通过环境反馈进行学习的思路。ADP方法主要包括三种基本类型启发式动态规划HDP、双启发式动态规划DHP和全局双启发式动态规划GDHP。近年来随着深度学习的发展深度强化学习Deep Reinforcement Learning将深度神经网络与强化学习相结合在Atari游戏、围棋AlphaGo、机器人控制等领域取得了突破性进展。这些算法背后的理论基础正是贝尔曼在七十年前提出的动态规划思想。另一方面神经算法推理Neural Algorithmic ReasoningNAR则尝试让神经网络直接学习算法的执行过程。研究表明神经网络可以被训练来模仿动态规划表的填充过程从而具备可解释、可泛化的解题能力。4.4 动态规划的跨领域应用动态规划的影响力远远超出了算法竞赛的范畴。在多个学科领域中动态规划都是解决优化问题的核心工具生物信息学基因序列比对Needleman-Wunsch算法、Smith-Waterman算法是动态规划的经典应用。通过动态规划可以找到两个DNA序列的最优比对帮助科研人员理解遗传信息和进化关系。经济学动态规划被广泛应用于资产配置、风险管理、最优消费与投资决策等问题。通过定义价值函数并递归求解贝尔曼方程经济学家可以找到在不确定性环境下的最优决策策略。运筹学与管理科学库存管理、生产调度、资源分配、设备更新等问题都可以用动态规划高效求解。自然语言处理隐马尔可夫模型中的维特比算法——用于在给定观测序列的情况下找到最可能的隐藏状态序列——本质上是动态规划在概率图模型中的应用。机器人学与最优控制动态规划以及其后继的近似动态规划被用于机器人的路径规划、运动控制和决策制定使机器人能够在复杂环境中自主行动。这些跨领域应用表明动态规划不仅仅是一种算法技巧更是一种具有普适性的问题求解思想。从纯粹的理论探索到大规模实际应用动态规划在过去七十年中走过了漫长而辉煌的道路。结语从1949年夏天贝尔曼第一次对多阶段决策问题产生兴趣到1950年正式提出动态规划并为之命名再到1957年出版经典著作《Dynamic Programming》动态规划走过了七十余年的发展历程。在这段历史中它从一个纯粹的数学工具逐步发展成为计算机科学中最重要的算法设计范式之一。在算法竞赛领域动态规划自1994年首次进入IOI以来一直是区分选手水平的关键题型。从最简单的“数字三角形”到复杂的“依赖背包”和“树形DP”动态规划题目的难度跨度极大考验的是选手的问题建模能力、状态抽象能力和递推推导能力。本文以洛谷上的18道经典题目为载体系统地介绍了各类动态规划题型的解题思路和技巧希望能帮助读者建立起对DP的系统性认识。动态规划的魅力在于它既是一种具体的算法技巧更是一种普适的思维方式——“将复杂问题分解为相互关联的子问题并充分利用子问题的解来构造原问题的解”。这种思想不仅在计算机科学中有着广泛的应用在经济学、生物学、运筹学等众多学科中也发挥着重要作用。展望未来随着机器学习和大数据技术的快速发展动态规划正在与神经网络、强化学习等领域深度融合。近似动态规划、深度强化学习、神经算法推理等新兴方向正在不断拓展动态规划的边界。可以说动态规划不仅没有过时反而在新的时代背景下焕发出更强的生命力。无论技术如何演进贝尔曼所奠定的“最优子结构”和“重叠子问题”这两个核心理念都将持续指引着我们在复杂世界中寻找最优解的探索之路。