如何知道何时需要动态规划
Source: Dev.to
最初发布于 LeetCopilot Blog
别再盲目猜测了。学习那些明确告诉你问题需要 DP 的信号，别在暴力解法上浪费 30 分钟。
你盯着一道 LeetCode 题目。它是 Medium 难度，涉及计数或优化。但它是 DP 吗？
你浪费了 20 分钟尝试贪心，结果在第 17 条测试用例上失败。你尝试递归，却出现栈溢出。最后你偷看了解答标签：
“这是一个经典的动态规划问题。”
当然是。但在写代码之前，你该怎么知道它是 DP 呢？
本指南为你提供一份 在动手写代码前识别 DP 题目 的检查清单。
TL;DR
- DP 题目有两个特征： 重叠子问题 + 最优子结构。
- 需要关注的关键词： “计数方式的数量”， “最小/最大路径”， “最长/最短子序列”。
- 递归测试： 如果你的暴力递归会多次计算相同的
(状态)，那就是 DP。 - 贪心灯号测试： 如果每一步选择局部最优并不能保证全局最优，那很可能是 DP。
- 常见类别： 斐波那契式序列、网格路径、背包变体、子串/子序列问题，以及 “选择或跳过” 的决策树。
两个核心属性
动态规划其实就是 “带缓存的聪明递归”。 若问题缺少这两个特征，就不是 DP。
属性 1：重叠子问题
在求解大问题的过程中，你会反复求解同一个小问题。
示例： 斐波那契。
- 计算
fib(5)需要fib(4)和fib(3)。 - 计算
fib(4)又需要fib(3)。 fib(3)被求解了两次。
测试方法： 能否画出一棵递归树，其中某些节点会重复出现？
如果可以 → 存在重叠子问题 → DP 可以帮助。
属性 2：最优子结构
最优解可以由子问题的最优解构造而成。
示例： 最短路径。
如果从 A 到 C 的最短路径经过 B，那么从 A 到 B 的路径也必须是到 B 的最短路径。
反例： 最长简单路径（不可重复访问节点）。
从 A 到 C 经过 B 的最长路径可能 不 使用从 A 到 B 的最长路径，因为那条路径可能占用了后面需要的节点。
没有最优子结构 → DP 不适用。
关键词红旗（题目描述线索）
以下短语几乎可以肯定是 DP：
| 短语 | 示例题目 | 为什么是 DP |
|---|---|---|
| “计数方式的数量” | 爬楼梯、不同路径 | 计数路径/组合 → 经典 DP。 |
| “最小/最大 成本/路径/和” | 零钱兑换、最小路径和 | 带约束的优化选择 → 需要 DP。 |
| “最长/最短 子序列” | 最长递增子序列 | 索引之间的子问题会重叠 → 适合 DP。 |
| “能否划分/分割 …” | 等和子集划分 | 决策过程需要记忆化 → 适合 DP。 |
如果题目要求 计数、最小/最大，或 最长/最短 某件事，并且带有约束条件，马上考虑 DP。
递归烟雾测试
快速现场测试：
- 写一个暴力递归解法。
- 为一个小输入画出递归树（例如
n = 4）。
检查点： 是否看到相同的参数在不同分支中出现多次？
示例： 零钱兑换
solve(amount = 11) → solve(10), solve(9), solve(6)
solve(10) → solve(9), …solve(9) 在不同分支中出现 两次 → 检测到重叠子问题 → 加入记忆化（DP）。
如果每个子问题都是唯一的，那只是普通递归（例如树遍历），不属于 DP。
常见 DP 题目原型
1. 斐波那契式序列
模式： dp[i] 依赖于 dp[i‑1]、dp[i‑2]、…
示例： 爬楼梯、打家劫舍、解码方式。
2. 网格遍历
模式： dp[row][col] 依赖于上方或左侧的格子。
示例： 不同路径、最小路径和、地下城游戏。
3. 背包变体
模式： 对每件物品，决定 “取还是不取”。
示例： 0/1 背包、等和子集划分、目标和。
4. 子串 / 子序列
模式： dp[i][j] 表示区间 [i, j] 的解。
示例： 最长回文子串、最长公共子序列、编辑距离。
5. 决策树（选择或跳过）
模式： 对每个元素，可以选择包含或排除。
示例： 零钱兑换、组合总和、单词拆分。
什么情况下不使用 DP
1. 贪心可行
某些优化问题具备 “贪心选择性质”，局部最优必然导致全局最优。
示例： 活动选择、跳跃游戏（某些情况下）。
测试： 每一步选最好的选项是否能保证整体最优？如果是，使用贪心。
2. 没有重叠子问题
如果每次递归调用都是唯一的，缓存没有意义。
示例： 生成所有排列或组合且没有剪枝。
3. 没有结构的 NP‑Complete 问题
某些问题（例如任意图上的旅行商问题）缺乏有效的 DP 解法。
步骤化识别流程
阅读题目时，按以下思路检查：
- 它要求计数/最小/最大/最长吗？ → +1 DP 分。
- 我能把它递归化吗？ → +1 DP 分。
- 子问题会重叠吗？ → +1 DP 分。
- 贪心方法会失败吗？ → +1 DP 分。
如果你累计 3 分以上，基本可以确定是 DP。
如何提升识别自信
- 刷 20+ 经典 DP 题目（如 Blind 75、Grind 75）。
- 在解题时标记类型： “这是网格 DP”。 “这是背包变体”。
- 一周后再做一次，检验是否还能快速识别模式。
像 LeetCopilot 的学习模式 这样的工具可以生成闪卡，让你仅凭题目描述就判断模式，而不写代码。
FAQ
Q: 题目可以既是 DP 又是贪心吗？
A: 很少。某些题目（如 Jump Game II）两种思路都能通过，但通常一种方法更优。
Q: 如果不确定怎么办？
A: 先写暴力递归。如果超时且看到重复调用，就加入记忆化——这就是 DP。
Q: DP 总是最快的解法吗？
A: 不一定。有时贪心或优化的 BFS 更快。DP 往往是最容易推导的结构化解法。
Q: 怎么确定状态维度？
A: 问自己 “子问题之间有什么变化？” 若只有一个索引 → 1 维 DP；若有两个索引或（索引、剩余容量）→ 2 维 DP。
Q: 应该先用自顶向下还是自底向上？
A: 自顶向下（记忆化）写起来更简单。自底向上（表格化）更高效，也更受面试官青睐。
结论
识别 DP 并非魔法，而是模式匹配。
- 留意 优化或计数 的提问。
- 在递归树中检查 重叠子问题。
- 确认 最优子结构 存在。
多练习后，你看到 “求 … 的方案数” 就会立刻想到：“啊，DP。1 维数组，可能是斐波那契式。”
这样 LeetCode 就不再是盲猜，而是系统化的解题过程。
如果你想要一个 AI 助手帮助你掌握 LeetCode 模式并准备面试，快去看看 LeetCopilot。