动态规划是软考算法设计题目中最容易让考生失分的专题之一。很多考生对它的理解停留在"把大问题拆成小问题"这一句含糊的表述上，结果一做题就发现连状态都定义不出来。本文从正式定义出发，逐层拆解动态规划的本质，再落到软考软件设计师下午题的高频考法，帮助考生建立一套可以复用的解题框架。
动态规划（Dynamic Programming，简称 DP）是一类求解多阶段决策过程最优化问题的算法设计方法。它的核心思想可以概括为一句话：把原问题分解为若干相互关联的子问题，先求解子问题，再根据子问题的解逐步构造出原问题的最优解。这里的"动态"一词并非指程序运行时的动态变化，而是指问题求解过程中每一阶段的决策都依赖于前面阶段已经确定的状态，从而形成一个随时间或阶段演进的决策序列。
从数学形式上看，动态规划处理的问题通常可以被描述为：在给定约束条件下，从一组可行方案中寻找使得某个目标函数取得最优值（最大值或最小值）的方案。它适用于具有特定结构的最优化问题，这种结构就是下面要详细展开的"最优子结构"和"重叠子问题"两大性质。理解这两大性质，是判断一道题能不能用动态规划解决、以及如何设计状态的关键。
许多教材会把动态规划和分治法放在一起对比，因为二者都遵循"分解、求解、合并"的框架。但二者的本质区别在于子问题之间是否相互独立。分治法（如归并排序、快速排序）把问题分解成互不重叠、相互独立的子问题，各子问题之间没有公共部分，每个子问题只求解一次，然后简单合并即可。动态规划处理的则是子问题之间存在大量重叠的场景，同一个子问题会被反复计算，若采用朴素递归，计算量会呈指数级增长。
举个最直观的例子：斐波那契数列的定义是 F(n)=F(n-1)+F(n-2)。如果直接用递归计算 F(5)，会发现 F(3) 被重复计算了多次。这种重复计算就是"重叠子问题"的典型表现。分治法不会遇到这种重复，而动态规划正是为消除这种重复计算而诞生的。理解这一点，也就理解了动态规划为什么会引入"记忆"机制——无论是自顶向下的备忘录法，还是自底向上的填表法，本质都是把已经算过的子问题结果保存下来，避免重复求解。
在软考体系中，动态规划主要出现在软件设计师下午科目的算法设计题中，也散见于系统分析师和系统架构设计师的综合知识题里。软件设计师下午题的第四道或第五道大题，常以 C 语言或伪代码的形式给出一个具体的动态规划问题，要求考生补齐缺失的代码语句或回答算法思想、时间复杂度和空间复杂度。常见的命题载体包括最长公共子序列、0-1 背包问题、矩阵连乘、最短路径等经典问题。
值得注意的是，软考对动态规划的考查往往不要求考生默写完整代码，而是考查考生对状态定义、状态转移方程、初始条件和边界条件的理解。因此，考生只要能把一个问题的状态和转移关系讲清楚，即便不精通某一种编程语言，也能拿到大部分分数。这也是本文把重点放在"状态定义"和"转移方程"上的原因。
动态规划的整个方法论建立在一个朴素的观察之上：一个问题的最优解，可以由它的子问题的最优解推导出来。这个观察被提炼为两个可以严格判定的性质，理解了这两个性质，就抓住了动态规划的命脉。
最优子结构（Optimal Substructure）是指：一个问题的最优解，包含了其子问题的最优解。换句话说，如果一个问题的最优解可以由子问题的解构造而来，并且构造过程中只依赖子问题的最优解，那么这个问题就具有最优子结构性质。
以 0-1 背包问题为例：有若干件物品，每件物品有重量和价值，背包有容量上限，要求在不超过容量的前提下使装入物品的总价值最大。这个问题的最优子结构表现为：在考虑前 i 件物品、容量为 j 的子问题中，其最优值要么包含第 i 件物品，要么不包含。无论哪种情况，剩下的部分都对应一个更小的子问题，而整个问题的最优解正是从这两个子问题的最优值中取较大者得到的。这种"当前决策 + 子问题最优"的递推结构，就是最优子结构最典型的形式。
需要强调的是，最优子结构并非所有问题都具备。有些问题的最优解不能由子问题的最优解组合而成，这时就不能用动态规划，或者需要对状态进行扩展。例如，最长路径问题在一般图中不具有最优子结构（因为路径可能重复经过顶点，子路径的最优不一定构成整体最优），而最短路径问题在无负权回路的情况下具有最优子结构。软考命题人有时会利用这一点设置辨析题，考查考生对动态规划适用条件的判断能力。
重叠子问题（Overlapping Subproblems）是指：在递归求解过程中，不同的递归分支会反复求解同一个子问题。这种重复是动态规划能够发挥优势的前提。若子问题完全独立，递归的分治就足够高效，动态规划反而增加了解题复杂度。
重叠子问题带来的后果是朴素递归的时间复杂度爆炸。仍以斐波那契数列为例，用朴素递归计算 F(n) 的时间复杂度约为 O(2 的 n 次方)，因为每个 F(n) 都展开成两个子问题，形成一棵指数规模的递归树，而树中存在大量重复的节点。动态规划通过把每个子问题的结果保存起来，使每个子问题只求解一次，从而把时间复杂度降到 O(n)。从指数级到线性级的跨越，正是动态规划价值的直观体现。
这里需要澄清一个常见的误解：重叠子问题强调的"重复计算"指的是递归树中相同的子问题被多次遇到，而不是"子问题数量多"。子问题数量多但互不重复，那是分治的适用场景。只有子问题既多又重复，才轮到动态规划出场。考生在判断算法选择时，应重点关注子问题是否被重复求解，而非单纯看问题能否被分解。
状态和状态转移方程是动态规划的两大核心构件，也是软考大题中分值最集中的部分。所谓状态，就是对子问题的一个精确、可判定的描述，它必须完整地刻画当前子问题所处的局面，使得从该状态出发，后续的决策只依赖该状态本身，而不依赖到达该状态的历史过程。这个性质称为"无后效性"，是状态定义是否合格的重要标准。
状态转移方程则描述了不同状态之间的递推关系，它回答了"当前状态的最优值如何由更小的状态的最优值推导出来"这一问题。以最长公共子序列为例，设两个字符串的前 i 个字符与前 j 个字符的最长公共子序列长度为 dp(i,j)，则状态转移方程为：当第 i 个字符与第 j 个字符相同时，dp(i,j)=dp(i-1,j-1)+1；当二者不同时，dp(i,j) 取 dp(i-1,j) 与 dp(i,j-1) 中的较大者。这个方程清晰地表达了"末字符是否匹配"这一关键决策，把复杂问题归结为三个更小子问题的最优值。
理解了状态和转移方程的本质，就能体会到动态规划设计的难度所在：最难的一步往往不是写出递推公式，而是正确定义状态。状态定义得过粗，会丢失必要信息，导致无后效性不成立；定义得过细，又会导致状态空间过大、效率低下。软考大题中"补全代码"的题目，本质上就是在考考生能否识别出题人预设的状态定义，并按该定义补全转移逻辑。
动态规划有两种等价的实现策略，分别对应"自顶向下"和"自底向上"两种思考方向。二者在结果上一致，但在代码形态、空间开销和思维习惯上有所差异。软考既考理解也考代码补全，因此两种路径都需要掌握。
备忘录法（Memoization）保留了递归的分治结构，但在递归过程中增加一个存储结构，把已经计算过的子问题结果保存下来。当递归再次遇到同一个子问题时，直接从存储结构中读取结果，不再向下递归。这种方法保持了递归代码直观易读的优点，同时把时间复杂度的指数增长压缩为与子问题总数成正比的多项式增长。
备忘录法的关键在于"先查后算"：进入一个子问题之前，先检查该子问题的结果是否已经存在，若存在则直接返回，若不存在才真正计算并存储。它适用于那些递归结构自然、但子问题重叠严重的问题。软考伪代码中若出现"若已计算则返回存储值"的判断语句，往往就是备忘录法的标志。
备忘录法与朴素递归的本质区别，在于用一张查找表把"计算"与"存储"绑定在一起。朴素递归只关心如何把问题拆开，对已经算过的结果毫不留情地丢弃，因此同一子问题会被反复展开；备忘录法则在每次递归返回时顺手把结果记入表，下次遇到同样的参数时直接查表。这种改动几乎不改变递归的逻辑结构，却能把时间复杂度从指数级拉回多项式级，是一种代价极小、收益极大的优化。软考综合知识题若比较两种方法的优劣，答案通常落在"备忘录法保留了递归的直观性，但需要额外的存储空间来保存子问题结果"这一点上，考生应能准确表述二者的时空权衡。
自底向上法（Bottom-up）是软考代码题中
本篇完！