玻尔百科为了实现最佳的整体结果而做出系列选择，是物流、金融等领域面临的一个基本挑战。最直观的路径——做出当前看起来最好的选择——从长远来看往往会导致次优结果。短期收益与全局最优之间的这种差距，暴露了简单“贪心”策略的局限性，并凸显了对一种更稳健的结构化决策方法的需求。本文介绍动态规划，这是一种强大的算法技术，旨在系统地为这类复杂问题找到可证明的最优解。
本文旨在全面介绍动态规划，从其核心理论到其现代影响。在“原理与机制”部分，我们将剖析最优子结构和重叠子问题这两个基本概念，并将动态规划的系统方法与常常出错的贪心方法进行对比。我们还将探讨其效率的微妙本质及其固有限制。随后，“应用与跨学科联系”部分将展示动态规划惊人的广泛性，介绍其在解决遗传学、计算科学乃至让有人工智能更透明、更易于理解等领域中的关键问题上的应用。
我们如何做出系列决策以实现最佳可能的结果？想象一下在迷宫中寻路、投资股市，或者仅仅是为旅行打包行李。在每一步，你都面临一个选择。做出正确的选择似乎很简单，但真正的挑战在于，一个早期的决定可能会让你走上一条当时看起来不错、但最终却通向死胡同或平庸结果的道路。你如何能确定今天的选择不会葬送你未来的成功？
这是算法设计学科所要解决的核心问题。两种强大的策略——贪心方法和动态规划——为寻找最优路径提供了截然不同的理念。
最直观的策略就是只做当前看来最好的事。想给某人找零？使用面额最大的硬币，以尽快减少所欠金额。这就是贪心算法的本质：在每一步都做出局部最优的选择——即当前看起来最有希望的选择——并且永不回头。对于许多日常问题，比如用标准的美国货币（1、5、10、25美分）找零，这种方法完美无缺。它感觉自然、高效且正确。
但让我们进入一个稍有不同的世界，这里有一套奇特的硬币面额：。假设我们需要找零12美分。贪心方法会首先选择不超过总额的最大面额硬币：美分硬币。我们还剩下美分要找。两枚美分硬币即可。结果是三枚硬幣：。这似乎很合理。
但这是我们能做到的最好结果吗？稍加思考就会发现另一种方式：两枚6美分硬币。这个方案只用了两枚硬币。我们的贪心策略，通过做出看似明智的10美分硬币的选择，将我们锁定在一条次优路径上。最初的局部最优决策是一个陷阱。这个简单的例子揭示了一个深刻的道理：一系列局部最优选择并不总能导向全局最优解。能让贪心算法奏效的性质被称为贪心选择性质，这是一个并非所有问题都具备的特殊特性。
如果我们不能相信自己的直接本能，我们能相信什么呢？让我们回到那个找零问题。12美分的最优解是。这个解是由两个更小的部分组合而成的。这暗示了一个更深刻、更可靠的原则。
让我们想象一下，我们已经找到了为某个金额 找零的最有效方法。该方案必然包含使用某一枚起始硬币，比如面额为 。如果我们拿走这枚硬币，剩下的硬币堆就是为剩余金额 找零。现在，关键的洞见来了：这堆剩下的硬幣必须是为 找零的最优方式。
为什么？假设它不是。假设存在一种更好、更有效的方式用更少的硬币为 找零。如果真是这样，我们可以直接用这个更好的方案，再加上我们的硬币 back to it, 这样我们就构造出一种用比原始“最优”方案更少的硬币为 找零的新方法。这是一个矛盾！因此，我们最初的假设必然是错误的；那个更小问题的解毕竟必须是最优的。
这个优美的性质被称为最优子结构：一个问题的最优解包含其子问题的最优解。这是动态规划的哲学核心。它给了我们一个保证——一条我们可以遵循的逻辑线索。我们无需对未来进行贪心猜测，而是可以通过正确地将来自过去的、更小的、完美解拼接起来，从而构建出一个完美的解。我们不必寄希望于自己走在正确的道路上；我们可以一步步地证明它。
最优子结构为我们提供了寻找最优解的蓝图。我们不是从顶层开始做决策，而是从底层开始，逐步向上构建。这就是动态规划中的“规划”（programming）——不是指写代码的编程，而是一个更古老的术语，意为“计划”或“制表”。我们正在系统地填充一个表格，记录所有更小子问题的答案。
让我们回到用我们那套奇怪的硬币 找零的问题。
当我们最终计算到 美分时，我们会评估：
最小值是 。我们有条不紊地、无可辩驳地找到了最优解。
这个过程之所以有效，是因为我们经常需要多次解决同一个子问题。一个朴素的递归方法会一遍又一遍地求解，比如说，。动态规划对每个子问题只求解一次，并将结果存储在一个表中（这个过程称为记忆化）。当再次需要这个答案时，只需快速查找即可。这种子问题被反复求解的特性被称为重叠子问题，它与最优子结构一起，是判断一个问题是否适合使用动态规划的第二个关键要素。
动态规划感觉像是对易出错的贪心方法的一次巨大飞跃。它似乎系统地驯服了复杂问题。但它到底有多快呢？让我们考虑经典的0-1 背包问题。我们有一组 个物品，每个物品都有重量和价值，我们想找到能装入容量为 的背包中且总价值最大的物品组合。像找零问题一样，简单的贪心策略（比如选择价值重量比最高的物品）可能会失败。
动态规划的解法是构建一个大小约为 的表格，其中对于每个物品 和每个可能的容量 ，我们存储可实现的最大价值。总运行时间与此表的大小成正比，即 。
这看起来很棒。它是一个两数之积，看起来像是一个多项式。一个学生在发现这一点后，可能会兴奋地宣称，既然背包问题是著名的“难”（NP完全）问题，这个多项式时间算法就证明了 P=NP，从而解决了计算机科学中最伟大的开放问题。
但这里存在一个美妙的微妙之处。在算法的正式研究中，“快”（即多项式时间）是相对于输入长度来衡量的，也就是写下输入所需的比特数。要表示数字 ，我们需要大约 个比特。要表示容量 ，我们需要大约 个比特。 本身的值与其比特长度相比可能非常巨大； 的大小可达 。
我们算法的运行时间是 。如果我们代入 ，运行时间就变成了 。这在表示容量的比特数 上是指数级的。一个运行时间在其输入的数值上是多项式的，但在其输入的比特长度上是指数级的算法，被称为伪多项式时间算法。它只有在所涉及的数字较小时才快。如果我们能保证 总是，比如说，小于 ，那么运行时间 将是输入规模的一个真正多项式。
一个有趣的思维实验证实了这一区别：如果我们用一元编码（unary）来表示输入，即数字5写成'11111'，会怎样？数字 的输入长度现在就是 本身。相对于这个臃肿的输入大小， 的运行时间现在是真正的多项式了。这揭示了“效率”的概念与我们如何表示信息密切相关。
动态规划似乎是一种通用的优化工具。它能解决任何具有最优子结构的问题吗？令人惊讶的是，答案是否定的。动态规划的力量受限于我们能否为子问题定义一个既充分又紧凑的“状态”。
在标准的背包问题中，我们的状态仅仅是 (item_index, current_weight)。这已经足够了，因为添加一个新物品的价值只取决于剩余的重量容量，而与已经选择了哪些具体物品无关。每个物品的价值贡献是独立的。
让我们来做一个改变。在二次背包问题（Quadratic Knapsack Problem）中，成对的物品可以产生协同效应。例如，打包一台笔记本电脑和它的充电器所提供的组合效用大于它们各自价值的总和。现在的目标函数包含了依赖于物品对的二次项，如 ，其中如果取物品 则 为 1，否则为 0。
让我们尝试应用我们的动态规划逻辑。当我们决定是否包含物品 时，它的总贡献不再仅仅是其基础价值 。它等于 加上与我们已经打包的其他物品的所有协同加成。为了计算这个，我们需要知道背包中已经存在的物品的确切子集。我们简单的 (item_index, current_weight) 状态已不再足够。它告诉我们已使用的总重量，但没有说明是哪些具体物品构成了这个重量。
一个正确的状态必须是类似 (item_index, current_weight, subset_of_items_chosen_so_far) 这样的东西。但是可能的子集数量是指数级的！我们的动态规划表格将有指数级的行数，算法将不比暴力搜索好。最优子结构的简单形式被打破了。用前 个物品填充重量为 的背包的“最优”方式不再是一个单一的概念；它取决于我们下一步打算做什么。
这就是动态规划力量的边界。它在那些世界状态可以由几个小数字概括的问题上表现出色。当选择的历史以复杂、相互关联的方式影响后续决策时，动态规划的基础——从小的、简单的子问题构建解决方案——就崩溃了。理解这个极限让我们更深刻地体会到计算复杂性这个丰富多彩的领域，其中一些问题屈服于优雅的结构，而另一些则顽固地难以处理。
既然我们已经揭示了动态规划的美丽核心——将一个庞大问题分解为可管理的片段并记住答案的艺术——我们现在可以踏上一段旅程，看看这个简单而深刻的思想将我们引向何方。你可能会倾向于认为它只是程序员的一个聪明技巧，一个解决谜题的小众工具。但这就像把望远镜称为看月亮的有趣玩具一样。实际上，动态规划是理解世界的一个强大透镜。它提供了一种语言来谈论最优选择、隐藏结构以及进化的过程，其应用领域涵盖遗传学、经济学和人工智能等截然不同的领域。在某种程度上，它是一种结构化推理的基本原则。
在其核心，科学中的许多问题都与比较有关。我们比较DNA序列以追溯进化历史；我们比较经济趋势以预测未来；我们比较流程以找到一种标准的、最优的做事方式。动态规划为此提供了终极工具包。
想象一下，你正试图在两个不同机场之间找到标准操作程序的“精髓”。空中交通管制员发出的指令可能略有不同，但一系列核心事件必须发生：启动、滑行、对准跑道、起飞、爬升。你如何通过计算提取这个共享的核心？这正是最长公共子序列（LCS）算法的完美工作。通过将指令流视为两个序列，动态规划可以筛选它们，并识别出两者共有的最长有序指令集，忽略一个机场独有的小变化或额外步骤。它找到了两条序列之间的共同线索，即共享的故事。
当我们把注意力从机场跑道转向生命的蓝图——DNA时，同样的逻辑具有了深远的意义。一位生物学家可能想知道人类和黑猩猩的血红蛋白基因有多相似。核苷酸序列——A、C、G、T——并非完全相同。经过数百万年的演变，发生了突变。一些碱基可能被删除，另一些则被插入。问题不仅在于找到一个公共子序列，而在于找到最佳的比对，即能最大化基于Watson-Crick碱基配对的分数的比对。经典的序列比对动态规划方法完美地解决了这个问题。
但如果生物学有更复杂的规则呢？假设我们想找到两股链之间最长的完美互补片段，但我们允许一个“凸起”（bulge）——即其中一条链上有一个未配对的核苷酸。我们的整个框架会崩溃吗？完全不会！这正是动态规划灵活性的闪光之处。我们只需丰富我们的记忆。我们不再仅仅记录在某点结束的最佳比对，而是记录两个值：没有凸起的最佳比对，和有一个凸起的最佳比对。递推关系稍微复杂一些，因为它现在必须考虑扩展一个无凸起的比对、扩展一个已有凸起的比对，或者创建一个新的凸起。但核心原则保持不变：从更小的、最优的片段构建解决方案。
然而，这种力量并非无限。如果我们想要比对的不是两条序列，而是几十条，以构建一个蛋白质的完整家族树呢？这就是多序列比对（MSA）的问题。原则上，我们可以扩展我们的动态规划框架。我们需要的不再是一个二维表格，而是一个用于 条序列的 维超立方体。但在这里，我们撞到了一堵墙——臭名昭著的“维度灾难”。计算成本随序列数量呈指数增长，大约为 ，其中 是序列长度。即使只有少数几条序列，这个数字也会变得天文般巨大，远超地球上任何计算机的能力。这给我们上了一堂计算科学中至关重要的一课：动态规划为我们指明了通往精确、完美解的道路，但它也清晰地定义了难解性的悬崖，精确地告诉我们在何处必须放弃对完美的追求，转而使用巧妙的启发式和近似方法。
生活是一系列选择，我们通常希望做出最好的选择。动态规划是按序做出最优决策的数学体现。
考虑一个简单而实际的问题：在两台计算机服务器之间平衡负载。你有一系列任务，每个任务都有一定的计算“权重”。你希望将一部分任务分配给第一台服务器，使其总负载尽可能接近目标容量，但又不超过它。一种简单的“贪心”方法可能是将任务从大到小排序，然后逐个装入。这看似直观，但常常无法找到最佳解。你可能会剩下少量未使用的容量，而这些容量本可以通过不同的小任务组合来完美填充。
相比之下，动态规划是耐心而彻底的。它不轻易做出承诺。它系统地构建一个表格，记录可以实现的所有可能的总负载。通过这样做，它保证能找到在容量范围内的绝对最佳组合。它解决了贪心方法失败的子集和（Subset Sum）问题（背包问题的一个变种）的最优解。
这种背包式思维与计算理论有着令人惊讶而美妙的联系。背包问题的动态规划算法的运行时间取决于物品的价值，而不仅仅是物品的数量。这被称为伪多项式时间算法。如果数字小，它就很快，但如果数字巨大，它就很慢。这听起来像是一个弱点，但实际上它是一个非凡技巧的关键。对于像背包问题这样的许多NP难问题，我们可以使用这种伪多项式DP作为完全多项式时间近似方案（FPTAS）的基础。这个想法非常巧妙：我们取原始物品的价值（可能很大且不方便），然后将它们按比例缩小并四舍五入。这使得新的最大价值变小，因此DP算法运行得非常快。当然，我们通过四舍五入引入了一些误差。但缩放是以一种非常聪明的方式进行的，由一个误差参数 控制，使得最终解中的误差可被证明是很小的——比如，在真实最优值的 以内。这是一个深刻的结果：一个（看似较弱的）伪多项式精确算法的存在，使我们能够为一个原本棘手的问题构造一个既快速又能保证接近最优答案的（非常强大的）算法。
这种最优划分的主题超出了离散物品的范畴。想象一下分析一个癌症基因组。科学家对单个细胞进行测序，并计算基因组的每个部分被读取了多少次。在健康细胞中，你期望每个染色体有两个拷贝。在癌细胞中，染色体的片段可能被删除（拷贝数为0或1）或扩增（拷贝数为3、4或更多）。原始数据是沿着基因组的带噪声的读取计数信号。目标是将这个信号划分为恒定拷贝数的片段。你如何决定断点在哪里？片段太多，你只是在拟合噪声；片段太少，你会错过真正的变异。DP提供了一个完美的解决方案。我们可以定义一个目标函数，它平衡了两个相互竞争的愿望：数据在一个片段内的拟合度（例如，最小化与片段均值的平方误差）和创建一个新片段的惩罚。然后，DP算法沿着染色体前进，找到可证明的最优断点集，以最小化这个总成本，从而优雅地从嘈杂数据中揭示潜在的基因组结构。
最后，我们转向动态规划展现其最纯粹数学之美的领域——利用隐藏结构，以及最令人惊讶地，使现代人工智能变得可以理解。
有些问题在其一般形式下是出了名的困难，但如果输入具有特殊结构，它们就会变得出奇地易于处理。顶点覆盖（Vertex Cover）问题是一个经典的例子。对于一个由节点和边组成的通用网络，找到“接触”到每条边的最小节点集是一个NP完全问题。但如果网络是一棵树——一个没有环的图呢？这种结构性约束是一把神奇的钥匙。我们可以使用DP。通过从叶子节点开始向上移动到根节点，我们可以计算每个子树的最小顶点覆盖的大小。每个节点的状态需要稍微聪明一些：我们计算两次答案，一次假设该节点在覆盖集中，一次假设它不在。这使我们能够在组合子节点的解时做出最优选择。树结构的存在（禁止环）确保了一个分支中的决策不会与另一个分支产生复杂的、长程的依赖关系，从而使DP能够施展其魔力，并在线性时间内解决问题。
DP也是计数的能手。考虑一个几个世纪以来一直让数学家着迷的纯组合问题：一个整数 可以有多少种方式写成正整数之和？这就是整数划分（Integer Partition）问题。划分的数量 增长得非常快。直接枚举是毫无希望的。然而，一个简单而优雅的DP算法可以轻松计算这些值。其洞见在于通过考虑所允许部分的大小来构建划分。我们可以通过将其与使用最大为 的部分的划分相关联，来计算使用最大为 的部分的 的划分数。这导出了一个可以用非常紧凑的方式实现的递推关系，填充一个划分数表格的运行时间仅仅是 的二次方。
也许DP最令人惊叹的现代应用在于对可解释人工智能（XAI）的追求。我们拥有强大的“黑箱”模型，如梯度[提升决策树](@entry_id:265930)，它们在医疗和金融领域做出关键预测。但模型为什么会做出某个特定的预测？为了建立信任，我们需要将预测归因于输入特征。Shapley值，一个源自合作博弈论的概念，为此提供了一种理论上合理的方法。然而，它的精确计算在计算上是一场噩梦，需要在指数级的特征组合上求和。多年来，这意味着我们只能使用粗略的近似。
然后出现了一个突破：对于基于树的模型，精确的Shapley值可以被高效地计算出来。这个名为TreeSHAP的算法是纯粹的动态规划。它遍历决策树，在每个节点，它不仅仅是做一个决策，而是跟踪所有可能遵循该路径的特征联盟的比例。当到达一个叶子节点时，它利用从根部传播下来的这些信息，将叶子节点的预测值归因回路径上的特征。该算法的复杂度虽然不小，但在树的深度和叶子数量上是多项式的，从而将一个指数级难的问题变成了一个可处理的问题。这是一个经典的算法原理为我们最先进的技术提供透明度和问责制的关键的美丽例子。
从寻找我们基因中的共同祖先，到在物流中做出可证明的优良决策，再到窥探人工智能的内部思想，动态规划的原则始终是一个强大而恒常的伴侣。它证明了这样一个理念：只要我们有智慧记住我们走过的路，最复杂的旅程也可以一步步地被理解。