动态规划完全指南：从入门到问题类型全解析

什么是动态规划？

**动态规划（Dynamic Programming，简称 DP）**是一种通过将复杂问题分解为更简单的、重叠的子问题来进行优化的技术。DP 不会多次求解相同的子问题，而是存储结果并重复使用。

软件工程类比

如果你熟悉软件架构，可以把 DP 理解为智能缓存：

软件概念	DP 对应概念
缓存/记忆化	存储计算结果的 DP 表
缓存命中	复用已存储的子问题解
缓存未命中	计算新的子问题
缓存键	状态（如 `dp[i]` 或 `dp[i][j]`）
缓存失效	不需要 - 子问题不会改变

核心洞察：DP 以空间换时间，通过存储中间结果来避免重复计算。

两个关键性质

一个问题要能用 DP 解决，必须具备以下两个性质：

1. 最优子结构（Optimal Substructure）

问题的最优解可以由其子问题的最优解构造出来。

例子：最短路径
最短路径 A → C = 最短路径 A → B + 最短路径 B → C

例子：斐波那契
F(n) = F(n-1) + F(n-2)

2. 重叠子问题（Overlapping Subproblems）

在递归过程中，相同的子问题会被多次求解。

F(5) 的递归调用树：
                    F(5)
                  /      \
               F(4)       F(3)      ← F(3) 被计算了两次！
              /    \      /    \
           F(3)   F(2)  F(2)  F(1)  ← F(2) 被计算了三次！
          /   \
       F(2)  F(1)

不用 DP，计算 F(5) 需要 15 次递归调用。用 DP，我们只需计算 6 个不同的值，每个只算一次。

自顶向下 vs 自底向上

实现 DP 有两种方法：

自顶向下（记忆化搜索）

从主问题开始，递归求解子问题，同时缓存结果。

优点：

更直观 - 符合自然的递归思维
只计算必要的子问题
对于复杂的状态转移更容易实现

缺点：

递归开销（栈空间）
输入过大时可能栈溢出

自底向上（递推/表格法）

从最小的子问题开始，逐步构建到主问题。

优点：

无递归开销
通常更容易进行空间优化
由于更好的缓存局部性，通常更快

缺点：

需要理解正确的迭代顺序
可能计算不必要的子问题

自顶向下: F(5) → F(4) → F(3) → F(2) → F(1) → F(0)  [递归]
自底向上: F(0) → F(1) → F(2) → F(3) → F(4) → F(5)  [迭代]

DP 五步框架

使用这个框架系统地解决任何 DP 问题：

第一步：定义状态

dp[i]（或 dp[i][j]）代表什么？

状态应该包含做出决策所需的所有信息。常见模式：

dp[i] = 前 i 个元素的答案
dp[i] = 以索引 i 结尾的答案
dp[i][j] = 子数组 [i, j] 的答案
dp[i][j] = 使用前 i 个物品、容量为 j 时的答案

第二步：找状态转移方程

如何从更小的子问题计算 dp[i]？

这是递推关系 - DP 的核心。问自己：

在状态 i 我有什么选择？
每个选择如何与之前的状态关联？

第三步：初始化边界条件

最小的子问题是什么？我们可以直接求解吗？

常见边界条件：

空输入：dp[0] = 0 或 dp[0] = 1
单元素：dp[1] = input[0]
边界值：dp[i][0] = ...，dp[0][j] = ...

第四步：确定迭代顺序

应该按什么顺序填充 DP 表？

规则：一个状态只能在它依赖的所有状态计算完成后才能计算。

如果 dp[i] 依赖 dp[i-1]，从小到大迭代 i
如果 dp[i] 依赖 dp[i+1]，从大到小迭代 i
对于 2D DP，考虑逐行或对角线顺序

第五步：提取结果

最终答案在 DP 表的哪里？

常见模式：

最后一个元素：dp[n] 或 dp[n-1]
最大/最小值：max(dp) 或 min(dp)
特定目标：dp[target]

交互式可视化：斐波那契

观察 DP 如何一步步构建解：

Loading visualization...

注意每个值只计算一次然后被复用！

交互式可视化：爬楼梯

Loading visualization...

代码演进：从递归到优化 DP

让我们看看从朴素递归到优化 DP 的演进过程：

复杂度对比

方法	时间	空间	备注
纯递归	$O(2^n)$	$O(n)$	指数级 - n > 40 会超时
记忆化	$O(n)$	$O(n)$	每个子问题只解一次
递推	$O(n)$	$O(n)$	无递归开销
空间优化	$O(n)$	$O(1)$	只保留需要的状态

通用 DP 模板

DP 问题类型大全

以下是你在面试中会遇到的 DP 问题类型全面整理：

类型一：线性 DP（一维）

定义： 状态依赖于单个序列中的前一个元素。

状态模式： dp[i] = 考虑元素 0 到 i 的最优值

经典问题：

爬楼梯 (LC 70)

状态：dp[i] = 到达第 i 阶的方法数
转移：dp[i] = dp[i-1] + dp[i-2]
本质上就是斐波那契！

打家劫舍 (LC 198)

状态：dp[i] = 抢劫房屋 0 到 i 的最大金额
转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
经典的”拿或不拿”模式

更多线性 DP 问题：

类型二：网格 DP（二维）

定义： 状态定义在二维网格上，通常用于路径问题。

状态模式： dp[i][j] = 到达格子 (i, j) 的最优值

经典问题：

不同路径 (LC 62)

状态：dp[i][j] = 到达 (i, j) 的路径数
转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界：dp[0][j] = dp[i][0] = 1

最小路径和 (LC 64)

状态：dp[i][j] = 到达 (i, j) 的最小路径和
转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

更多网格 DP 问题：

类型三：字符串 DP

定义： 在一个或两个字符串上的 DP，通常用于匹配/编辑问题。

状态模式： dp[i][j] = s1[0..i] 和 s2[0..j] 的答案

经典问题：

最长公共子序列 (LC 1143)

状态：dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
转移：
  如果 s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
  否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

编辑距离 (LC 72)

状态：dp[i][j] = 将 s1[0..i-1] 转换为 s2[0..j-1] 的最小操作数
转移：
  如果 s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
  否则: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                       (替换)         (删除)     (插入)

更多字符串 DP 问题：

类型四：背包 DP

定义： 在有约束（重量、数量）的情况下选择物品以优化价值。

状态模式： dp[i][w] = 使用前 i 个物品、容量为 w 时的最优值

经典问题：

零钱兑换 (LC 322)

状态：dp[amount] = 凑成 amount 所需的最少硬币数
转移：dp[i] = min(dp[i], dp[i - coin] + 1) 对每种硬币
边界：dp[0] = 0

分割等和子集 (LC 416)

状态：dp[i][sum] = 使用前 i 个元素能否凑出 sum？
转移：dp[i][s] = dp[i-1][s] || dp[i-1][s - nums[i]]
（0/1 背包变体）

更多背包 DP 问题：

类型五：区间 DP

定义： 状态由区间 [i, j] 定义，通过组合更小的区间求解。

状态模式： dp[i][j] = 子数组/子串 [i, j] 的最优值

经典问题：

最长回文子序列 (LC 516)

状态：dp[i][j] = s[i..j] 中的 LPS 长度
转移：
  如果 s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
  否则: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

戳气球 (LC 312)

状态：dp[i][j] = 戳破范围 (i, j) 内气球获得的最大硬币
转移：dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
     对所有 k 属于 (i, j)

更多区间 DP 问题：

类型六：子序列 DP

定义： 寻找最优子序列（不一定连续）。

经典问题：

最长递增子序列 (LC 300)

状态：dp[i] = 以索引 i 结尾的 LIS 长度
转移：dp[i] = max(dp[j] + 1) 对所有 j < i 且 nums[j] < nums[i]
时间：O(n²)，可用二分查找优化到 O(n log n)

更多子序列 DP 问题：

类型七：状态压缩 DP（位掩码 DP）

定义： 使用位掩码表示集合状态，通常用于子集/排列问题。

状态模式： dp[mask]，其中 mask 是表示已选元素的位掩码

经典问题：

划分为k个相等的子集 (LC 698)

状态：dp[mask] = mask 中的元素能否被分成若干组？
使用位掩码跟踪哪些元素已被使用

更多位掩码 DP 问题：

类型八：树形 DP

定义： 在树结构上的 DP，通常使用后序遍历。

状态模式： dp[node] = 以 node 为根的子树的最优值

经典问题：

打家劫舍 III (LC 337)

状态：对每个节点，记录 [抢劫时的最大值, 不抢时的最大值]
转移：
  rob_current = node.val + not_rob_left + not_rob_right
  not_rob_current = max(left) + max(right)

更多树形 DP 问题：

类型九：博弈 DP

定义： 两个玩家都采取最优策略的博弈问题。

状态模式： dp[i] = 从状态 i 开始，当前玩家的最优得分差

经典问题：

石子游戏 (LC 877)

状态：dp[i][j] = 在 piles[i..j] 中，当前玩家的最大得分差
转移：dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

预测赢家 (LC 486)

与石子游戏类似，但返回玩家1是否能获胜。

时间与空间复杂度模式

DP 类型	典型时间	典型空间	空间优化
线性 1D	$O(n)$	$O(n)$	滚动变量可到 $O(1)$
网格 2D	$O(m \times n)$	$O(m \times n)$	逐行处理可到 $O(n)$
字符串（双串）	$O(m \times n)$	$O(m \times n)$	可到 $O(min(m,n))$
背包	$O(n \times W)$	$O(n \times W)$	可到 $O(W)$
区间	$O(n^2)$ 到 $O(n^3)$	$O(n^2)$	通常无法优化
位掩码	$O(2^n \times n)$	$O(2^n)$	通常无法优化

何时不使用 DP

DP 并非万能。在以下情况考虑其他方法：

1. 没有重叠子问题

如果子问题不重叠，递归或分治就足够了。

例子：二分查找、归并排序
每个子问题只解一次 - 缓存没有收益。

2. 贪心有效

如果每步的贪心选择能导向最优解，DP 就是大材小用。

例子：活动选择、霍夫曼编码
贪心：O(n log n)，DP：O(n²) - 用贪心！

3. 状态空间太大

如果 DP 表太大，考虑其他方法。

例子：如果状态是 dp[i][j][k]，空间 n³ 且 n > 1000
考虑：近似算法、启发式方法或不同的建模方式

4. 问题是 NP-Hard

有些问题没有多项式时间的 DP 解。

例子：旅行商问题（除非 n 很小可用位掩码 DP）

DP 问题识别清单

看到问题时，问自己这些问题：

“求最小/最大…” → 很可能是 DP
“计算有多少种方法…” → 很可能是 DP
“是否可能…” → 很可能是 DP（布尔 DP）
“给定选择约束…” → 很可能是背包 DP
“博弈最优策略…” → 很可能是博弈 DP

信号词：

“最大”、“最小”、“最优”
“方法数”、“计数”
“最长”、“最短”
“子序列”、“子串”
“能否实现”、“是否可能”

总结：核心要点

DP = 递归 + 记忆化（或智能迭代）
两个关键性质： 最优子结构 + 重叠子问题
五步框架：
- 定义状态
- 找状态转移
- 初始化边界条件
- 确定迭代顺序
- 提取结果
掌握这些核心类型：
- 线性 DP → 打家劫舍
- 网格 DP → 不同路径
- 字符串 DP → 编辑距离
- 背包 DP → 零钱兑换
- 区间 DP → 戳气球
空间优化： 通常可以只保留必要的前置状态
练习识别 DP 问题：寻找优化关键词和重叠子结构

下一步

本文介绍了基础知识。在后续文章中，我们将深入探讨每种 DP 类型：

线性 DP 精通 - 进阶模式与优化
网格 DP 问题 - 从基础到复杂变体
字符串 DP 深入 - 编辑距离、正则匹配等
背包问题家族 - 0/1背包、完全背包、多维背包
区间 DP 技巧 - 矩阵链乘法等
位掩码 DP - 何时以及如何使用状态压缩
树形 DP - 树结构问题的模式
博弈 DP - Minimax 与最优策略

敬请期待！