动态规划解题方法论

📖 目录

• 适用场景
• 核心原理
• 具体做法：4 步通用流程
• 决策辅助：3 种决策类型
• 实战案例
• 安全锁清单
• 进阶方向

一、适用场景

这篇是写给谁的？ —— 正在刷 LeetCode 动态规划题、感觉 "知道 dp 是啥但碰到新题还是不会" 的学习者。

如果你符合以下任意一条，这里适合你：

• ✅ 你能看懂题解里的转移方程，但自己想不出来
• ✅ 你刷了十几道 DP 题，换道新题还是无从下手
• ✅ 你听说过"最后一步分析法"，但不知道怎么套

什么时候不适合看这篇？ —— 如果你完全不知道什么是 DP（先去看基础概念），或者你已经能独立做 medium DP 题了（这篇对你太浅）。

二、核心原理

30 秒讲清本质

flowchart LR
    subgraph forward["正向思维 (易迷路)"]
        direction LR
        A1["第1步怎么走"] --> A2["第2步怎么走"] --> A3["..."] --> A4["第n步怎么走"]
    end

    subgraph backward["DP 思维 (倒着想)"]
        direction LR
        B1["目标: 第n步的结果"] --> B2{"最后一步做了什么选择"}
        B2 --> B3["选择1 - 子问题规模 n-1"]
        B2 --> B4["选择2 - 子问题规模 n-2"]
        B3 --> B5["递推关系 f(n) = ..."]
        B4 --> B5
    end

一句话口诀：顺着想会迷路，倒着想有公式。

为什么这样有效？

大多数人拿到 DP 题，本能反应是从头开始推："第一个元素怎么处理？第二个怎么处理？..." 很快就会陷在细节里。

反过来看：跳过前 n-1 步，只看最后一步。

假设问题已经解决了，答案已经在手上了。问自己三个问题：

1️⃣  在得到最终答案之前的那「最后一步选择」，我做了啥？
     （爬楼梯 → 最后跨了 1 步还是 2 步？）

2️⃣  做了这个选择之后，「剩下的部分」变成了什么规模更小的子问题？
     （把最后 1 步去掉 → 剩下的是 n-1 规模的同一问题）

3️⃣  最后一步有几种不同的可能？都列出来，取最优或求和。

你不需要从头规划整个决策链条，只需要想清楚"末端发生了什么"，然后相信相同逻辑能递归回去。

朴素方案 vs DP

三、具体做法：4 步通用流程

在白纸上按这个步骤画，不要跳步：

注意： 递推关系的思考方向是从 n 到 n-1/n-2（倒着推），但填表的方向是从 0 到 n-1（正着算）。因为计算依赖：要算 dp[5]，需要 dp[4] 和 dp[3] 已经算好了。

四、决策辅助：3 种决策类型

在草稿纸上先判断当前题目属于哪种选择。每种配了一句口诀：

类型 A："选或不选"（0-1 背包变体）

类型 B："枚举最后一刀"（区间 DP）

类型 C："多条路径汇合"（网格 / 线性递推）

五、实战案例

例 1：爬楼梯

题目：每次可以爬 1 或 2 个台阶，爬到第 n 阶有几种方法？

映射表：4 步流程 → 本题实现

Step 1：定义状态

思考过程：问题问的是"爬到第 n 阶有几种方法" → 那 dp[i] 很自然地定义为"爬到第 i 阶的方法数"。

dp[i] = 爬到第 i 阶的方法数

Step 2：分析最后一步

假设已经爬到第 n 阶了。前一刻只能有两种可能：

flowchart LR
    A[当前在第 n 阶] --> B{前一刻在哪}
    B --> C[第 n-1 阶 · 跨 1 步]
    B --> D[第 n-2 阶 · 跨 2 步]
    C --> E["f(n) = f(n-1) + f(n-2)"]
    D --> E

Step 3：写出方程

f(n) = f(n-1) + f(n-2)

转换成 dp 下标：
dp[i] = dp[i-1] + dp[i-2]    (i ≥ 2)

Step 4：边界与顺序

最小的 n 直接心算：

dp[0] = 1   第 1 阶：只有 [1]
dp[1] = 2   第 2 阶：可以是 [1+1] 或 [2]

验证递推：

dp[2] = dp[1] + dp[0] = 2 + 1 = 3  → [1+1+1, 1+2, 2+1] ✓
dp[3] = dp[2] + dp[1] = 3 + 2 = 5  → [1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2] ✓

代码实现

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * n
        dp[0] = 1  # 第 1 阶
        dp[1] = 2  # 第 2 阶
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n-1]

朴素版本用了 O(n) 空间。观察发现 dp[i] 只依赖前两个值，可以压到 O(1)：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

例 2：打家劫舍

题目：一排房间，每个房间有现金 nums[i]，不能偷相邻的两家，求最大偷窃金额。

映射表：4 步流程 → 本题实现

Step 1：定义状态

为什么这样定义？ 尝试直接定义"第 i 间"容易卡住，因为偷了 i 就不能偷 i-1。用范围最优（0~i 范围能拿到的最大值）更自然，不要求一定偷 i。

dp[i] = 从第 0 间到第 i 间（包含），能偷到的最大金额

Step 2：分析最后一步

来到最后一间房，两个选择：

Step 3：写出方程

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Step 4：边界与验证

dp[0] = nums[0]                   ← 只有一个房间，只能偷它
dp[1] = max(nums[0], nums[1])     ← 两个房间，选钱多的

验证 [100, 1, 1, 1000]：

dp[0] = 100
dp[1] = max(100, 1) = 100
dp[2] = max(dp[1], dp[0] + nums[2]) = max(100, 100+1) = 101
dp[3] = max(dp[2], dp[1] + nums[3]) = max(101, 100+1000) = 1100 ✓

代码实现

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[n-1]

空间优化（只依赖前两个状态）：

class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        prev2, prev1 = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
        return prev1

六、安全锁清单

6.1 dp 数组大小怎么定？

长度 = n     → 一般对应输入规模，下标 0~n-1
长度 = n+1   → 下标 0 做 dummy/边界，下标 1~n 对应实际数据

经验： 如果递推式里出现了 dp[i-2]，数组长度至少为 n。如果 dp[0] 对应第一个元素，那 dp[n-1] 就是答案。

6.2 下标从 0 还是 1 开始？

用从 0 开始的下标 + 题目描述的自然语言做对照：

常见错误： 递推式里 i 从 1 开始循环但写成了 dp[i-2] 导致下标变负。解决：统一让 i 从 2 开始循环。

6.3 什么时候用一维 dp，什么时候用二维？

6.4 dp[i-2] 不保证偷了 i-2，用起来放心吗？

放心。dp[i-2] 是 0~i-2 范围的最优解，不管它具体怎么选，i-2 和 i 之间隔着 i-1，一定不会相邻。

所以 dp[i-2] + nums[i] 永远是一个合法方案，不需要知道 dp[i-2] 的内部细节——这就是 DP 的"黑盒"抽象。

6.5 循环方向搞反了怎么办？

6.6 递推关系推出来了，但答案不对？

按这个排查顺序走：

① 检查 dp 数组定义 → 和问题结果对得上吗？
② 检查边界条件 → dp[0]/dp[1] 手算验证了吗？
③ 检查递推下标 → dp[i] 依赖的是 dp[i-1] 还是 dp[i-2]，写对了没？
④ 检查循环范围 → 从哪到哪？最后一个下标覆盖到了吗？
⑤ 检查返回值 → dp[n-1] 还是 max(dp)?

七、进阶方向

变种题目

学习路线

爬楼梯（入门）→ 打家劫舍（线性DP）→ 不同路径（二维DP）
→ 0-1 背包（选或不选）→ 完全背包（无限取用）
→ 最长递增子序列（LIS）→ 最长公共子序列（LCS）
→ 区间DP（戳气球）→ 树形DP（打家劫舍 III）

优化方向

• 空间优化：大部分二维 DP 可以压成一维（滚动数组）
• 状态压缩：当状态是集合时用位运算替代数组（如旅行商问题）
• 四边形不等式：某些区间 DP 的 k 枚举范围可以剪枝
• DP + 二分：LIS 的 O(n log n) 优化

记住：DP 不是玄学，是"暴力枚举 + 聪明缓存"。递推关系靠从结尾往前想得出，代码实现靠从 0 到 n 正向填表。先学会定义状态，再谈优化。如果卡住了，回到最小规模手动枚举，找到规律再泛化。