动态规划：给“最优解”一张记住过去的备忘录
武侠小说中，高手决斗时会反复试探对方的招式套路，一旦看破就永远记住，下次相同招式袭来就能瞬间破解——这背后的思维正是动态规划的核心：用记忆化避免重复计算，将大问题拆解为可复用的小问题解决方案。
假设你面前有10级台阶，每次可以跨1级或2级，有多少种方法登顶？如果你从最后一步倒推：登上第10级台阶的前一步，要么从第8级跨2级，要么从第9级跨1级。那么问题就变成了：到达第10级的方法数 = 到达第8级的方法数 + 到达第9级的方法数——这就是动态规划最朴素的思维雏形。
01 动态规划是什么？从“笨方法”到“聪明递归”
动态规划是一种通过把原问题分解为相对简单的子问题的方式，来高效求解复杂问题的算法思想。它的核心智慧是：记住你已经解决过的子问题答案，避免重复计算。
一个经典对比：斐波那契数列
求第n个斐波那契数（每个数是前两个数之和：1, 1, 2, 3, 5, 8…）
暴力递归（笨方法）：
deffib_naive(n):ifn<=2:return1returnfib_naive(n-1)+fib_naive(n-2)# 大量重复计算！计算
fib(7)时，fib(5)会被计算多次，像一棵急剧膨胀的递归树。动态规划（聪明方法）：
- 自顶向下记忆化搜索：给递归函数加个“备忘录”，算过的结果存起来。
memo={}deffib_memo(n):ifn<=2:return1ifninmemo:returnmemo[n]# 查备忘录memo[n]=fib_memo(n-1)+fib_memo(n-2)# 存备忘录returnmemo[n] - 自底向上递推：从小问题开始，一步步推导到大问题。
deffib_dp(n):dp=[0]*(n+1)dp[1]=dp[2]=1foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]# 状态转移方程returndp[n]
这两种动态规划方法都将时间复杂度从指数级 O(2ⁿ) 降到了线性 O(n)，本质是用空间换时间，用记忆化换取高效能。
- 自顶向下记忆化搜索：给递归函数加个“备忘录”，算过的结果存起来。
02 核心思想：两大基石与一个方程式
动态规划能高效解决问题的前提，是问题具备以下两个关键性质，并可以用一个方程描述其递推关系。
1. 最优子结构
大问题的最优解可以由其子问题的最优解组合得到。
就像拼乐高，整体最稳固的结构，必然由每一层最稳固的拼接方式组成。
- 正面例子：最短路径问题。从A到C的最短路径如果经过B，那么这条路径中A到B、B到C的部分也必然是各自段内的最短路径。
- 反面例子：象棋最优棋步。即使最终赢了，中盘的某一步可能并非局部最优，需要为全局牺牲。这种问题就不具备最优子结构。
2. 重叠子问题
在递归求解过程中，相同的子问题会被反复计算多次。
斐波那契数列就是典型例子。动态规划的价值，就在于识别并消除这种冗余计算。
flowchart LR A[“原问题”] --> B{“是否具有<br>最优子结构？”} B -->|否| C[无法使用标准动态规划] B -->|是| D{“是否具有<br>重叠子问题？”} D -->|否| E[考虑更简单的<br>分治或贪心算法] D -->|是| F[适合应用动态规划] F --> G[“定义‘状态’<br>（用什么参数描述子问题）”] G --> H[“确定‘状态转移方程’<br>（子问题如何推导出父问题）”] H --> I[“确定‘基础状态’<br>（最小子问题的解）”]3. 状态转移方程
这是动态规划的“灵魂公式”，是对最优子结构的数学描述。它定义了如何从已知子问题的解，推导出当前问题的解。对于斐波那契数列，状态转移方程就是：dp[i] = dp[i-1] + dp[i-2]
其中dp[i]这个“状态”代表“第 i 个斐波那契数的值”。
03 经典问题解析：0/1背包问题
理论讲完了，来看一个动态规划的“毕业考”经典题：0/1背包问题。
问题描述：你有一个容量为 W 的背包，面前有 n 件物品。第 i 件物品重量为weight[i]，价值为value[i]。每件物品只能拿或不拿（0或1）。如何选择物品，使得背包中物品总价值最大？
关键点解析：
- 定义状态：我们需要一个能表示“考虑范围”和“容量约束”的状态。定义
dp[i][w]为：只考虑前 i 件物品，在背包容量为 w 的情况下，能获得的最大价值。 - 状态转移方程：对于第 i 件物品，我们只有两种选择：
- 不放入背包：那么最大价值就等于“只考虑前 i-1 件物品、容量为 w”时的最大价值，即
dp[i-1][w]。 - 放入背包（前提：当前容量 w >= 物品 i 的重量）：那么最大价值就等于“物品 i 的价值”加上“只考虑前 i-1 件物品、容量为
w - weight[i]”时的最大价值，即value[i] + dp[i-1][w - weight[i]]。
我们要的是最大价值，所以取两者中的最大值：dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])
- 不放入背包：那么最大价值就等于“只考虑前 i-1 件物品、容量为 w”时的最大价值，即
- 基础状态：当没有物品可选（i=0）或背包容量为0（w=0）时，最大价值自然为0。
填表示例：假设背包容量 W=4，物品如下：
物品1：重量2，价值3
物品2：重量3，价值4
物品3：重量1，价值2
我们构建的dp表如下（横向为容量 w，纵向为考虑前 i 件物品）：
| i\w | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1(物1) | 0 | 0 | 3 | 3 | 3 |
| 2(物1,2) | 0 | 0 | 3 | max(3, 4+0)=4 | max(3, 4+0)=4 |
| 3(物1,2,3) | 0 | 2 | max(3, 2+0)=3 | max(4, 2+3)=5 | max(4, 2+3)=5 |
最终解：dp[3][4] = 5，即选择物品2（重3，值4）和物品3（重1，值2），总重为4，总价值为5。
04 动态规划的两种实现方式
从背包问题的填表过程，可以清晰看到动态规划的两种实现路径：
1. 自顶向下（记忆化搜索）
- 思路：从目标问题开始递归分解，遇到计算过的子问题就直接从备忘录（如数组、字典）中读取结果。
- 优点：思维直接，通常只计算必要的子问题。
- 缺点：递归有栈开销。
- 适用：子问题空间不是所有都需要计算的情况。
2. 自底向上（递推填表）
- 思路：从最小的基础状态开始，逐步迭代计算并填充表格，直到得到目标问题的解。
- 优点：效率稳定，无递归开销，便于分析。
- 缺点：可能需要计算所有子问题。
- 适用：绝大多数动态规划问题，尤其是竞赛和面试中最常见的形式。
选择建议：对于初学者，强烈建议从“自底向上”的递推填表法开始练习。它强迫你明确地定义状态和转移方程，是理解动态规划本质的最佳途径。
05 动态规划 vs. 贪心算法 vs. 分治算法
为了帮你更好地区分这些易混淆的算法思想，这里有一个对比表格：
| 特性 | 动态规划 | 贪心算法 | 分治算法 |
|---|---|---|---|
| 核心思想 | 记忆化+递推，先解决子问题并记录，再组合出大问题的解。 | 每一步都做当前看似最优的选择，希望导致全局最优。 | 分而治之，将大问题分解为独立的小问题，分别解决后合并。 |
| 关键性质 | 最优子结构、重叠子问题 | 最优子结构、贪心选择性质 | 子问题独立不重叠 |
| 决策方式 | 当前决策依赖所有相关子问题的解 | 当前决策只依赖当前状态 | 子问题决策相互独立 |
| 解的正确性 | 保证全局最优 | 不一定全局最优 | 保证正确（因为只是分解与合并） |
| 典型问题 | 背包问题、最短路径、编辑距离 | 分数背包、哈夫曼编码、活动选择 | 归并排序、快速排序、棋盘覆盖 |
| 效率 | 通常较高（避免重复计算） | 通常最高（直接选择） | 取决于合并开销 |
一个精辟的比喻：
- 分治算法像管理一家大公司，把业务拆分成独立子公司（子问题），各自经营（求解）后再汇总报表（合并）。
- 贪心算法像短线交易者，每天只根据当天行情（当前状态）做出最优买卖，不理会长期影响。
- 动态规划像老谋深算的棋手，每走一步前，都会基于之前推演过的所有棋局（子问题解），计算出能导向最终胜利的最优走法。
06 如何识别并解决动态规划问题？
当你遇到一个新问题时，可以尝试以下步骤：
第一步：判断是否适用DP
- 问题是否求最优解（最大、最小、最长、最短）？
- 问题能否被分解为相似的子问题？
- 子问题之间是否存在重叠？（如果难以直接判断，先假设有重叠去设计）
第二步：设计DP方案（“四步法”）
- 定义状态：用一组参数清晰地描述一个子问题。通常用数组
dp[i]或dp[i][j]表示。 - 推导状态转移方程：找出
dp[i]与dp[i-1]、dp[i-2]… 等更小子问题之间的关系。这是最核心也最难的一步。 - 确定基础状态：找出最小的、不能再分解的子问题的解，作为递推的起点。
- 确定计算顺序：是自顶向下递归，还是自底向上递推？确保在计算
dp[i]时，它所依赖的子问题状态都已被计算过。
第三步：优化（进阶）
- 空间优化：观察状态转移方程，如果
dp[i]只依赖于前面有限的几个状态（如dp[i-1]和dp[i-2]），就可以用几个变量滚动更新，代替整个数组，将空间复杂度从 O(n) 降到 O(1)。 - 维度优化：在背包问题中，通过改变遍历顺序，有时可以将二维
dp表优化为一维数组。
07 现代应用：从算法题到真实世界
动态规划绝不只是算法竞赛的玩具：
- 生物信息学：DNA序列比对（Needleman-Wunsch算法）的核心就是动态规划。
- 自然语言处理：机器翻译、语音识别中，用于计算最优的词序列匹配（维特比算法）。
- 金融经济：期权定价、资产配置、消费储蓄的最优决策模型。
- 计算机视觉：图像分割、特征匹配等任务中寻找最优边界或对应关系。
- 工业决策：资源调度、生产计划、路径规划等优化问题。
动态规划的精髓，在于它教会计算机一种**“基于经验的智慧”：不再重复踏入同一条河流，不再重复计算同一个问题。它把最复杂的全局决策，拆解成一系列可被记忆、可被复用的局部决策。下次当你面对一个看似庞大复杂的问题时，不妨问问自己：“这个问题的最小版本是什么？我如何能从解决这些最小版本开始，像搭积木一样，构建出最终答案？”** 这，就是动态规划给你的思维礼物。
