动态规划是软考软件设计师、系统分析师、系统架构设计师等科目算法部分绕不开的核心考点。每年考试中，命题人都会设置一道题目，要求考生在分治、贪心、动态规划、回溯、分支限界五种经典算法设计策略中，判断某个具体问题应当采用哪种策略，或者直接要求计算一个动态规划问题的具体结果。不少考生背下了动态规划这个名字，却始终讲不清楚它和贪心、分治的本质区别，一遇到需要推导状态转移方程的题目就束手无策。本文从动态规划的定义出发，深挖最优子结构与重叠子问题两大核心性质，剖析它与贪心、分治的边界，再结合矩阵连乘、零一背包两道真题的计算过程，把命题套路和答题要点讲透。
动态规划（Dynamic Programming，简称 DP）是一种用于求解具有特定结构的最优化问题的算法设计技术。它的核心思想是把一个规模较大的原问题分解为若干个规模较小的子问题，先求解这些子问题、再合并子问题的解，最终得到原问题的解。这里必须强调一个关键限定：动态规划所处理的子问题之间必须是重叠的，同一个子问题会在求解过程中被多次遇到。如果每次遇到都重新计算，就会造成大量重复劳动，动态规划的价值恰恰在于把每个子问题的解保存下来，后续直接取用，从而把指数级的时间复杂度降低为多项式级别。
从形式化的角度看，动态规划处理的对象通常是多阶段决策过程：问题的求解划分为若干相互联系的阶段，每一阶段都要做出一个决策，前一阶段的决策影响后一阶段的可用状态，整条决策序列的优劣由一个目标函数衡量。动态规划方法由美国数学家理查德·贝尔曼在二十世纪五十年代提出，他同时给出了最优性原理：一个最优策略的子策略，对于它自己对应的子问题而言也必然是最优的，这正是最优子结构性质的原始表述。
在软考教材与标准术语体系中，动态规划通常被表述为：把原问题分解成相互重叠的子问题，采用自底向上或自顶向下的方式，通过保存子问题的解避免重复计算，从而求解最优值的一种算法设计方法。教材特别强调两个判断条件：问题具有最优子结构性质，且子问题之间存在重叠。二者缺一不可，是动态规划区别于其他算法策略的分水岭。值得注意的是，动态规划与分治法外观相似，都把问题分解为子问题再合并，但分治法要求子问题相互独立、互不重叠，动态规划恰恰要求子问题相互重叠，这是二者最本质的分歧。
最优子结构性质，是指原问题的最优解包含了其子问题的最优解。以矩阵连乘问题为例，设矩阵链从第 i 个矩阵连乘到第 j 个矩阵的最少乘法次数为 m[i][j]，那么这个问题的最优解必然在某一个分割点 k 处断开，先计算左侧子链 m[i][k] 与右侧子链 m[k+1][j] 的最优解，再把两部分合并。如果左侧子链没有采用最少乘法次数，那么整个矩阵连乘的乘法次数也不可能达到最少，这就说明矩阵连乘问题具有最优子结构。
最优子结构是动态规划正确性的根基。正是因为最优解可以递归地由子问题的最优解构造，我们才敢放心地自底向上填表。需要提醒考生的是，最优子结构与"重叠子问题"是两回事，一个问题的子问题可能不重叠但依然具有最优子结构，此时它更适合用分治法或直接递归求解，而不必动用表格存储机制。
重叠子问题性质，是指在用递归方式求解问题的过程中，同一个子问题会被反复计算多次。最典型的例子是斐波那契数列的朴素递归实现：要计算第 n 项，需要分别计算第 n 减 1 项和第 n 减 2 项，而计算第 n 减 1 项时又需要计算第 n 减 2 项和第 n 减 3 项，于是第 n 减 2 项被计算了两次，第 n 减 3 项被计算了三次，重复计算的数量随问题规模呈指数增长。动态规划把已算过的子问题结果存入表格，下次遇到直接查表，每项只计算一次。
重叠子问题性质是动态规划与分治法的根本区别。分治法处理的子问题彼此独立，像归并排序、快速排序那样不存在重复计算，因此直接用递归即可。而动态规划面对的子问题相互交叠，不保存结果就会把时间复杂度拖到无法接受的地步。可以这样概括：重叠子问题是动态规划"为什么要用表格"的理由，最优子结构是动态规划"为什么填表就能得到正确答案"的理由。
理解动态规划不能停留在"背了定义"的层面，必须深入到它从问题抽象到最终求解的完整机制中。一次完整的动态规划求解，通常要经过状态定义、状态转移方程推导、边界条件确定、计算顺序安排、解的重构这五个环节，任何一个环节出错都会导致最终答案错误，而软考的命题人恰恰喜欢在这些环节上设置陷阱。
状态是动态规划中最基础的概念，它是对子问题所处局面的完整描述。以零一背包问题为例，状态通常定义为：前 i 件物品、在背包容量为 w 的限制下所能获得的最大价值，记为 f[i][w]。这个状态包含两个维度，一个是"考虑了哪些物品"，一个是"剩余多少容量"。状态定义的要点在于"无后效性"，即某个状态的值被确定后，其后续演化只依赖当前状态本身，而与该状态如何到达无关。
状态转移方程是把不同状态联系起来的桥梁。零一背包问题的状态转移方程为 f[i][w] 等于 f[i-1][w] 与 f[i-1][w-wi] 加 vi 两者中的较大者，其中 wi 与 vi 分别是第 i 件物品的重量和价值。这个方程的含义是：对于第 i 件物品，要么不选它，此时最优值就是前 i 减 1 件物品在容量 w 下的最优值；要么选它，此时必须在前 i 减 1 件物品、容量减少 wi 的基础上加上它的价值。取两者较大值，就得到全局最优。状态转移方程是动态规划的灵魂，凡涉及动态规划计算的题目，核心就是要求考生正确写出或理解这个方程。
动态规划的实现方式分为两种。第一种是自底向上的方式，也叫迭代法或制表法，从最小的子问题开始，按照规模由小到大的顺序逐个计算，把结果填入表格，直到算出原问题的解。矩阵连乘问题就是典型：先计算所有长度为二的子链，再计算长度为三的子链，逐步扩展。第二种是自顶向下的方式，也叫备忘录法，沿用递归框架，但在递归入口处先检查该子问题是否已计算过，若已计算则直接返回缓存结果。两种方式的时间复杂度在渐进意义下相同，区别在于自底向上常数更小、无需递归栈，自顶向上代码更贴近自然的递归定义。
软考真题在考察这一层时，常常直接问"采用自底向上的方法实现该算法的时间复杂度是多少"。矩阵连乘问题自底向上填表需要填充一张 n 乘 n 的表，每填一个格子要遍历一个分割点 k，因此时间复杂度是 O(n³)，空间复杂度是 O(n²)。这类复杂度结论是命题人反复使用的考点，考生应当牢记。
动态规划的一个隐含要求是，在计算某个状态之前，它依赖的所有子状态都必须已经计算完成，这个要求决定了表格的填充顺序。在矩阵连乘中，m[i][j] 依赖的是 m[i][k] 和 m[k+1][j]，其中 k 介于 i 与 j 之间，因此必须先计算长度较短的子链，再计算较长的，填充顺序按子链长度递增进行。在零一背包中，f[i][w] 依赖 f[i-1] 这一行的值，因此按行从上到下填充。一旦填充顺序出错，某个状态在计算时就会引用到尚未就绪的垃圾值。软考有时给出一张已填好的表格，要求判断某个空缺格子的值，这实际上就是考察对填充顺序和转移方程的综合理解。
动态规划并不是一个单一算法，而是一族算法设计思想的统称。根据问题的结构特征，动态规划可以归纳出若干经典模型，每个模型都有标准的状态定义和转移方程。掌握这些模型，考生在考场上就能快速识别题型、套用模板，而不必每次从零开始推导。
区间型动态规划的特点是以"从第 i 个元素到第 j 个元素的区间"作为状态，通过枚举区间的分割点来转移。矩阵连乘是最典型的区间型动态规划。给定 n 个矩阵，第 i 个矩阵的规模为 p[i-1] 行 p[i] 列，要求确定加括号的方式使总乘法次数最少。状态 m[i][j] 表示从第 i 个矩阵连乘到第 j 个矩阵所需的最少乘法次数，转移方程在前面已给出，其物理含义是枚举最后一次乘法的分割点 k，两侧各自取最优，再加上合并所需的 p[i-1] 乘 p[k] 乘 p[j] 次标量乘法。区间型动态规划还包括最优二叉搜索树、石子合并等经典问题。
背包型动态规划以"物品集合与容量"作为状态，零一背包是其代表。所谓零一背包，是指每件物品要么完全装入、要么完全不装，不能只装一部分。它与分数背包形成鲜明对比：分数背包允许装入物品的一部分，因此可以采用贪心策略，按单位价值从高到低依次装入，保证得到最优解；而零一背包因为物品不可分割，贪心策略会失效，必须依赖动态规划。软考真题多次围绕这一对比设题，要求判断"哪个问题能用贪心算法保证求得最优解"，答案永远是分数背包而非零一背包。零一背包的时间复杂度为 O(nW)，其中 W 是背包容量，这是一个伪多项式时间复杂度，考生理解即可。