当前位置：首页 > news >正文

一文吃透动态规划：通用解题框架 + 实战案例

news 2026/5/12 11:48:04

动态规划（Dynamic Programming，简称DP）是算法领域的核心思想之一，也是面试、竞赛中的高频考点。很多人觉得DP“难”，本质是没抓住其核心逻辑——用空间换时间，通过记录子问题的最优解，避免重复计算。本文将拆解动态规划的通用解题框架，并结合经典案例落地，帮你彻底掌握DP的解题思路。

一、动态规划的核心本质

动态规划解决的是具有重叠子问题和最优子结构的最优化问题：

重叠子问题：原问题拆解后的子问题会被重复计算（比如斐波那契数列中，计算f(5)需要f(4)和f(3)，计算f(4)又需要f(3)和f(2)，f(3)被重复计算）；
最优子结构：原问题的最优解可以由子问题的最优解推导而来（比如凑零钱的最少硬币数，可由更小金额的最少硬币数推导）。

DP的核心就是用一个数组（DP数组）记录子问题的解，让每个子问题只计算一次，将暴力递归的时间复杂度从指数级降到多项式级。

二、动态规划通用解题框架（五步核心）

所有DP问题都可以按照以下五步拆解，这是一套可复制、可迁移的解题模板，从简单的零钱兑换到复杂的背包问题、最长公共子序列都适用。

第一步：定义DP数组/状态的含义（灵魂）

这是DP解题的“第一步，也是最关键一步”——明确DP数组的每个元素代表什么，定义错了后续全错。

DP数组的维度由问题的“状态维度”决定：

一维DP：适用于单状态问题（如零钱兑换、斐波那契数列）。
示例（零钱兑换）：dp[i]表示“凑成总金额i所需的最少硬币数量”；
二维DP：适用于双状态问题（如01背包、最长公共子序列）。
示例（01背包）：dp[i][j]表示“前i个物品，背包容量为j时能装的最大价值”；
示例（最长公共子序列）：dp[i][j]表示“字符串1的前i个字符和字符串2的前j个字符的最长公共子序列长度”。

核心原则：让DP状态能覆盖所有子问题，且子问题的解能推导出原问题的解。

第二步：确定Base Case（基准条件）

Base Case是“无需计算就能直接确定的最小子问题解”，是DP计算的“起点”，所有后续推导都依赖它。

经典案例的Base Case：

零钱兑换：dp[0] = 0（凑0元需要0枚硬币，这是最基础的子问题）；
斐波那契数列：dp[0] = 0，dp[1] = 1；
01背包：dp[0][j] = 0（前0个物品，价值为0）、dp[i][0] = 0（背包容量为0，价值为0）。

核心原则：Base Case必须是“无依赖的最小子问题”，不能再拆解，且值是确定的。

第三步：推导状态转移方程（核心逻辑）

状态转移方程是DP的“核心”，描述了“大问题”和“小问题”之间的递推关系——如何通过已计算的子问题解（如dp[i-1]、dp[i][j-1]）推导当前问题的解（dp[i]、dp[i][j]）。

经典案例的状态转移方程：

零钱兑换（求最小值）：
```
if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1)
```
解释：凑金额i的最少硬币数 = 所有“凑i-coin的最少硬币数 + 1枚当前硬币”中的最小值。
斐波那契数列（求累加）：
```
dp[i] = dp[i - 1] + dp[i - 2]
```

01背包（求最大值）：

# 不选第i个物品：价值 = dp[i-1][j] # 选第i个物品：价值 = dp[i-1][j - weight[i]] + value[i] dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])

核心原则：状态转移方程必须体现“最优子结构”——原问题的最优解由子问题的最优解组合而成。

第四步：确定遍历顺序

遍历顺序的核心是：计算当前DP值时，它依赖的所有子问题值已经被计算完成，否则会出现“用未更新的初始值计算，导致结果错误”。

经典案例的遍历顺序：

零钱兑换（一维DP）：
- 外层：金额从1到amount（从小到大）；
- 内层：遍历所有硬币。
  原因：dp[i]依赖更小的dp[i - coin]，必须先算完小金额，再算大金额。
01背包（二维DP）：
- 外层：物品从1到n；
- 内层：容量从1到bag。
  原因：dp[i][j]依赖dp[i-1][j]和dp[i-1][j-weight[i]]，必须先算完前i-1个物品的所有容量。

反例警示：如果零钱兑换的金额从大到小遍历，dp[i - coin]还未被计算（仍是初始值），最终结果会完全错误。

第五步：处理最终结果（边界/特殊情况）

最后一步是从DP数组中提取原问题的答案，并处理“无解”“边界输入”等特殊情况，不能直接返回DP数组的最后一个值。

经典案例的结果处理：

零钱兑换：
```
return dp[amount] if dp[amount] <= amount else -1
```
解释：初始值设为amount + 1（表示“不可达”），若最终dp[amount]仍大于amount，说明无法凑出该金额，返回-1。
最长公共子序列：
```
return dp[len(s1)][len(s2)]
```
解释：直接返回两个字符串完整长度对应的DP值，无需额外判断。
特殊输入处理：比如零钱兑换中amount = 0时，直接返回0（提前处理可简化逻辑）。

三、实战落地：用框架解零钱兑换问题

结合上述五步框架，完整实现零钱兑换问题，帮你串联整个解题流程：

defcoinChange(coins,amount):# 1. 定义DP数组：dp[i]表示凑金额i的最少硬币数# 2. Base Case + 初始化：dp[0]=0，其余设为amount+1（表示不可达）dp=[amount+1]*(amount+1)dp[0]=0# 4. 确定遍历顺序：先遍历金额（从小到大），再遍历硬币foriinrange(1,amount+1):forcoinincoins:# 3. 状态转移方程ifcoin<=i:dp[i]=min(dp[i],dp[i-coin]+1)# 5. 处理最终结果：判断是否可达returndp[amount]ifdp[amount]<=amountelse-1# 测试案例print(coinChange([1,2,5],11))# 输出3（5+5+1）print(coinChange([2],3))# 输出-1（无法凑出）