扫码获取 VIP 码
添加管理员微信获取 VIP 码
在软考软件设计师与系统架构设计师的算法设计题中，动态规划是出现频率极高、分值稳定的一类考点。很多考生第一次接触动态规划时，会误以为它是一种像冒泡排序、快速排序那样有固定步骤的具体算法，实际上并非如此。动态规划的英文全称是 Dynamic Programming，其中 Programming 一词在这里的含义不是"编写程序"，而是"规划、列表化求解"。动态规划是一套用于求解具有特定结构的最优化问题的方法论，它把原问题分解为若干相互关联的子问题，通过求解子问题并把子问题的解保存下来，逐步构建出原问题的最优解。
动态规划这一术语的提出者是美国数学家理查德·贝尔曼，他在二十世纪五十年代研究多阶段决策过程的最优化问题时创造了这个名词。当时的"Programming"更多地取"规划"之意，强调把复杂问题逐层展开、按表格形式推进求解的过程。理解这一点很重要，因为它揭示了动态规划的本质：它不是某一种固定的代码套路，而是一种把大规模问题分解为有依赖关系的小规模问题，并自底向上或带记忆地逐层求解的通用思想。同一个动态规划思想，可以落地为递归加备忘录，也可以落地为循环填表，形式可以变化，但思想内核不变。
从教材的标准定义看，动态规划适用于具有两个核心性质的问题。第一个性质是最优子结构，指的是原问题的最优解包含其子问题的最优解，也就是说，可以通过子问题的最优解推导出原问题的最优解。第二个性质是重叠子问题，指的是在递归求解过程中，同一个子问题会被反复计算多次。这两个性质缺一不可，它们共同决定了动态规划为什么有效，也决定了动态规划与分治法、贪心法之间的本质区别。
要理解动态规划在算法体系中的位置，需要把它和另外两种经典思想放在一起对照。分治法同样把问题分解为子问题，但分治法分解出的子问题是相互独立的，比如归并排序把数组一分为二，左右两半的排序互不影响，不存在重复计算。贪心法则是每一步都做出当前看起来最优的选择，并且假设局部最优能够累积成全局最优，它不回头、不保存历史。而动态规划恰恰介于两者之间：它的子问题相互重叠，一个子问题的解可能被多个父问题引用，所以必须把解保存下来，避免重复计算；同时它又要保证每一步的决策能够在全局意义上达到最优。
动态规划解题的全过程，可以概括为三个紧密咬合的环节：定义状态、枚举决策、写出转移方程。决策指的是从当前状态出发可以选择的所有动作，比如 0-1 背包中每件物品的选与不选，爬楼梯中走一步还是走两步。状态记录了当前所处的位置，决策规定了可以前进的方向，而状态转移方程则把状态与决策结合起来，给出做出某个决策后状态的取值变化。三者缺一不可：没有状态，决策失去落脚点；没有决策，转移无从谈起；没有转移方程，状态之间就无法递推。掌握动态规划，本质上就是熟练驾驭状态、决策、转移方程这三件套。
动态规划的一切都围绕"状态"展开。所谓状态，是指问题在某一阶段所处的完整描述，它必须能够唯一地确定后续求解所需的全部信息。以经典的爬楼梯问题为例，假设一次可以爬一阶或两阶，那么"已经到达第若干阶"就是一个状态，因为只要知道当前处于第几阶，就能确定接下来有几种走法。状态的选取直接决定了动态规划能否成功，状态定得好，问题迎刃而解；状态定得不好，要么无法刻画问题的全貌，要么导致状态空间爆炸。
状态的设计有两个基本要求。第一是状态必须完备，也就是状态所包含的信息要足以支撑后续的决策，不能丢失关键变量。第二是状态要尽量精简，冗余的状态维度会带来额外的计算开销。在软考真题里，很多丢分点恰恰出现在状态定义环节，考生往往急于列方程，却忽略了对状态含义的清晰界定，导致后续转移方程写得似是而非。
状态的维度直接决定了动态规划的时间复杂度和空间复杂度。如果状态是一维的，复杂度往往是线性的；如果状态是二维的，复杂度通常是平方级别的；如果问题需要在三个维度上刻画状态，复杂度就会上升到立方级别。因此，压缩状态维度是动态规划优化的重要手段，也是软考中一道有区分度的考查点。
状态转移方程描述了相邻状态之间的递推关系，它是动态规划的骨架。用数学语言表达，就是用一个函数式关系把某个状态的值，与它的前驱状态的值联系起来。仍以爬楼梯为例，若用 f(n) 表示到达第 n 阶的方法数，那么到达第 n 阶只能从第 n 减一阶走一步，或者从第 n 减二阶走两步，于是得到转移方程 f(n) 等于 f(n-1) 与 f(n-2) 之和。
写出状态转移方程之后，还需要确定边界条件，也就是递推的起点。爬楼梯问题的边界是 f(1) 等于 1、f(2) 等于 2。边界条件与转移方程共同构成了递推的完整定义，缺一不可。很多考生在考场上能够写出转移方程，却在边界条件上出错，导致后续所有结果连锁出错，这是软考命题人惯用的失分陷阱。
一个高质量的状态转移方程，应当满足两个标准：一是完备，能够覆盖所有可能的决策分支；二是无后效性，即某个状态一旦确定，它之后的发展只取决于当前状态本身，而与到达该状态的具体路径无关。无后效性是动态规划得以成立的重要前提，如果一个问题的状态会受历史路径影响，就需要在状态中额外加入历史信息，否则动态规划无法直接套用。
动态规划的经典实现路径有三个层次。第一个层次是朴素递归，它直观但会重复计算同一个子问题，时间复杂度往往呈指数级增长。第二个层次是记忆化搜索，也叫备忘录法，它在递归的基础上增加一个存储结构，把已经计算过的子问题解保存起来，下次遇到直接查表返回，从而把指数级复杂度降为多项式级。第三个层次是自底向上的递推，也就是按照状态的依赖顺序从小到大逐层计算，用循环代替递归，进一步避免了函数调用的开销。
这三个层次本质上是同一种思想的不同实现，软考选择题经常围绕它们设置辨析题。比如问"记忆化搜索与自底向上递推的关系"，正确答案是两者都能求解动态规划问题，前者是自顶向下加查表，后者是自底向上逐层填表，二者在本质上等价，区别仅在于计算顺序和实现形式。
在实际编程中，自底向上的递推往往还能配合滚动数组做空间优化。所谓滚动数组，是指当状态转移方程只依赖相邻的几项时，不必为所有状态开辟完整的存储空间，而是用少数几个变量循环复用，从而把空间复杂度从高维降到低维。例如爬楼梯问题只需保存前两个值，斐波那契类递推都能用两个变量滚动求解，这是软考中常考的空间优化技巧。
0-1 背包是动态规划最经典、最常考的问题模型。给定若干件物品，每件物品有重量和价值两个属性，还有一个容量有限的背包，要求选出若干件物品装入背包，使得总重量不超过背包容量的前提下，总价值最大。由于每件物品要么选、要么不选，只有两种状态，因此称为 0-1 背包。
设 f(i, j) 表示从前 i 件物品中选，装入容量为 j 的背包所能获得的最大价值，那么对于第 i 件物品，如果不选，则价值保持为 f(i-1, j)；如果选，则价值为 f(i-1, j-w) 加上第 i 件物品的价值。取两者的较大者即为状态转移方程。0-1 背包的变体很多，包括完全背包、多重背包等，其中完全背包是指每件物品可以选任意多次，软考中常以 0-1 背包为基础展开命题。
0-1 背包还有一个重要的空间优化结论值得牢记：当采用一维数组表示时，容量维度必须从大到小倒序遍历，这样才能保证每件物品只被选取一次。如果从小到大正序遍历，同一件物品就会被重复计入，问题就退化成了完全背包。这个正序与逆序的区别，是软考选择题和计算题里反复出现的考点。完全背包问题则是 0-1 背包的另一种变形，它允许每件物品取任意多次，因此容量维度改为正序遍历即可。完全背包的转移方程与 0-1 背包形式相同，只是遍历方向相反，这一正一反的对偶关系，正是软考命题人最爱拿来设置的辨析陷阱，考生务必把两个遍历方向对应的物理意义想清楚。
最长公共子序列问题是动态规划在字符串处理领域的经典应用。给定两个序列，求它们的最长公共子序列的长度。子序列不要求连续，但要求保持原序列中的相对顺序。设两个序列分别为 X 和 Y，用 f(i, j) 表示 X 的前 i 个字符与 Y 的前 j 个字符的最长公共子序列长度，那么当两个末尾字符相同时，f(i, j) 等于 f(i-1, j-1) 加一；当末尾字符不同时，f(
本篇完！