动态规划是软考软件设计师考试中算法设计板块的高频考点，几乎每年都会以选择题或下午题的形式出现。不少考生把动态规划理解为"背几个经典问题的模板"，遇到稍微变化的题目就无从下手，其根本原因在于没有吃透动态规划赖以成立的两个数学性质——最优子结构与重叠子问题。本文不从套路出发，而是回到这两个性质的技术本质，把动态规划的状态定义、状态转移方程、自顶向下与自底向上两种实现方式讲清楚，再结合软件设计师历年真题逐题拆解，帮助读者真正掌握这一考点。
动态规划（Dynamic Programming）是一种求解最优化问题的算法设计策略，其核心思想是把一个复杂的问题分解成若干相互关联的子问题，先求解子问题，再通过子问题的解逐步推导出原问题的最优解。这里的"Programming"并非指编写计算机程序，而是指一种规划、制表的方法论。动态规划这一名称源于二十世纪五十年代美国数学家理查德·贝尔曼的研究，他当时借用这个术语来规避军方对"研究"一词的审查，结果这个命名一直沿用至今。
在算法教材中，动态规划通常被定义为：将待求解问题分解为若干子问题，通过求解子问题并保存其结果，避免重复计算，从而高效地得到原问题最优解的方法。与分治策略不同的是，分治所划分的子问题往往是相互独立的，而动态规划所分解出的子问题之间存在重叠关系，即同一个子问题会被多次计算。动态规划之所以有效，正是因为它抓住了这种重叠，用空间换时间，把指数级的时间复杂度降为多项式级。
一个能够用动态规划求解的问题，必须同时满足两个条件。第一个条件是问题具有最优子结构性质，即原问题的最优解包含其子问题的最优解，或者说原问题的最优解可以由子问题的最优解组合而成。第二个条件是子问题具有重叠性，即用递归方式自顶向下求解时，会有大量子问题被重复计算。这两个条件缺一不可，前者保证了动态规划求解的正确性，后者保证了动态规划求解的高效性。
许多考生在辨析题中分不清动态规划、分治与贪心三者的界限，这是命题人最爱设置的陷阱之一。分治法将问题划分为互不相交的子问题，递归求解后合并，其典型代表是归并排序与快速排序；贪心法每一步都做出当前看来最优的选择，希望局部最优能累积成全局最优，其典型代表是Dijkstra最短路径算法与哈夫曼编码；而动态规划则在子问题重叠的场景下，通过记忆化或填表的方式避免重复计算，其典型代表是0-1背包问题与矩阵连乘问题。
三者的关键分野在于子问题之间的关系。分治的子问题彼此独立，不存在重叠；贪心不做全局规划，只做局部选择，因此贪心不一定能得到全局最优解，只有当问题具备贪心选择性质时贪心才正确；动态规划则通过枚举所有可能的决策并保存中间结果，保证得到全局最优解。用一句话概括：分治解决独立子问题，贪心在特殊结构上做局部决策，动态规划在重叠子问题上做全局规划。
值得注意的是，动态规划与分治在形式上颇有相似之处，二者都是把大问题拆成小问题，这导致不少考生单凭"拆分子问题"就判定一道题用动态规划，结果误入歧途。区分二者的关键在于拆分出来的子问题是否重叠：归并排序把数组一分为二，左右两部分互不重叠，各自独立求解后合并即可；而矩阵连乘问题中，子问题"前三个矩阵的最优连乘次序"会同时出现在多个更大问题的求解过程中，存在大量重复。凡是子问题之间相互独立、可以各自为战的场景，用分治更自然；凡是子问题之间有依赖、有重叠的场景，才轮到动态规划登场。
理解动态规划的底层机制，关键在于理解它如何利用问题的数学结构来降低计算量。这一部分我们从最优子结构、重叠子问题以及状态转移方程三个层面，逐一剖析动态规划"为什么能算得快"和"为什么能算得对"。
最优子结构性质是动态规划正确性的基石。它的含义是：如果一个问题的最优解可以被拆分成若干部分，那么每一部分都必须是其对应子问题的最优解。换句话说，原问题的最优解不会由任何子问题的非最优解组合而成。以最短路径问题为例，如果从起点到终点的最短路径经过某个中间节点，那么从起点到这个中间节点的路径、以及从这个中间节点到终点的路径，都必然是最短路径，否则用更短的子路径替换后能得到更短的总路径，这与"最短"的假设矛盾。
最优子结构的意义在于，它允许我们把求解原问题的任务，转化为求解若干规模更小的子问题。正是因为有这个性质，动态规划才可以放心地"只保留子问题的最优解"，而无须关心子问题的其他次优解。这一点是动态规划与穷举法的本质区别：穷举法需要遍历所有可能解，而动态规划通过最优子结构性质剪掉了大量不可能成为最优解的分支。
重叠子问题性质是动态规划高效性的来源。如果一个递归算法在求解过程中会多次遇到完全相同的子问题，那么这个问题就具有重叠子问题性质。最典型的例子是斐波那契数列的朴素递归实现，计算第n项时需要计算第n-1项和第n-2项，而计算第n-1项时又要计算第n-2项和第n-3项，导致第n-2项被重复计算多次。随着n增大，重复计算的次数呈指数级增长，时间复杂度从O(n)退化为O(2的n次方)。
动态规划的做法是，每当求得一个子问题的解，就把它保存下来，下次遇到相同的子问题时直接查表取用，不再重新计算。这种"记忆化"的思想用额外的存储空间换取了计算时间的大幅下降。对于0-1背包这类问题，朴素递归的时间复杂度是指数级的，而动态规划通过一张二维表将其降到O(n乘W)，其中n是物品数量，W是背包容量，效率提升是数量级的。
动态规划的求解过程，本质上是对"状态"的递推。所谓状态，是对问题在某一阶段所处局面的完整描述，它包含了从该局面出发继续求解所需的全部信息。状态的定义是动态规划中最关键也最困难的一步，状态定义得好，转移方程水到渠成；状态定义得不好，整个推导都会陷入混乱。
状态转移方程描述了不同状态之间的递推关系，即如何从已知的较小状态的值，推导出当前状态的值。以0-1背包为例，用f(i,j)表示考虑前i个物品、背包容量为j时所能获得的最大价值，那么状态转移方程为：如果第i个物品放得下，则f(i,j)取"不放入第i个物品"与"放入第i个物品"两者的较大值。这个方程完整刻画了"每个物品要么选、要么不选"的0-1决策，是动态规划从数学描述落到代码实现的桥梁。
写好状态转移方程，通常要回答三个问题。第一，当前状态可以由哪些更小的状态推导而来，这决定了方程等号右侧有哪些项；第二，这些更小的状态之间是取最大值、最小值、求和还是其他运算，这取决于问题是最大化、最小化还是计数；第三，推导是否有前提条件，比如0-1背包中"放入第i个物品"这一分支只有在物品重量不超过当前容量时才成立。把这三个问题回答清楚，转移方程就不会写错。可以说，动态规划的题做得好不好，最终都归结为"状态是否定义得完整"与"转移是否覆盖了所有决策"这两个判断。
动态规划并不是一个单一的算法，而是一类解题范式。根据实现方式和问题结构的不同，动态规划可以划分为若干经典模型。掌握这些模型，是应对软考算法题的基础。
动态规划有两种典型的实现路径。第一种是自顶向下的备忘录法，它保持递归的思考方式，从原问题出发，遇到子问题先查备忘录，若已计算过则直接返回，否则递归求解后存入备忘录。第二种是自底向上的填表法，它先求解最小规模的子问题，再按照依赖顺序逐层向上递推，直到求出原问题的解，通常用一个数组或一张表来存储中间结果。
两种方法在时间复杂度上等价，区别在于思考习惯与空间控制。备忘录法贴近递归定义，实现直观，但存在递归调用栈的开销；填表法迭代执行，常数因子更小，且便于分析空间复杂度。在软考中，矩阵连乘问题常要求考生写出自底向上的递推式并计算填表顺序，因此考生尤其要熟悉填表法的执行过程。
0-1背包问题是动态规划最经典的入门模型，也是软考反复出现的热点。问题描述为：给定n个物品，每个物品有重量和价值，以及一个容量为W的背包，每个物品要么完整装入、要么不装，问如何选择物品使装入背包的总价值最大。这里的"0-1"指的就是每个物品只有选与不选两种状态。
用动态规划求解时，定义状态f(i,j)为考虑前i个物品、背包剩余容量为j时的最大价值。对第i个物品，若其重量超过当前容量j，则只能不选，f(i,j)等于f(i-1,j)；若放得下，则在不选与选之间取较大值，选的价值等于该物品价值加上f(i-1,j减去该物品重量)。最终答案是f(n,W)。通过这个递推式，所有中间状态被组织成一张(n+1)行、(W+1)列的二维表，自左向右、自上而下
本篇完！