动态规划基础

动态规划是面试中最难理解的算法，但也是面试官最想考察的能力。关键不是背模板，而是理解为什么可以用 DP，以及如何定义状态。

面试考察点

面试官通过这道题想考察：
1. 你是否理解 DP 的核心思想——重叠子问题和最优子结构
2. 你是否能找到问题的最优子结构
3. 你是否能正确地定义状态和状态转移
4. 你是否能判断什么时候用 DP vs 其他算法

---

一、什么是动态规划？（核心概念）

1.1 从一个经典问题开始

面试官追问："什么是动态规划？为什么这个问题要用 DP？"

先看一个经典问题：斐波那契数列

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)，n >= 2

计算 F(5) 的递归树：

           F(5)
          /    \
       F(4)    F(3)
      /    \   /    \
    F(3)  F(2) F(2) F(1)
    /  \
  F(2) F(1)
  / \
F(1) F(0)

问题：F(3) 被计算了 2 次！F(2) 被计算了 3 次！
随着 n 增大，重复计算指数级增长！

1.2 DP 的核心思想

DP 的两个核心概念：

1. 重叠子问题
   子问题被重复计算多次
   （F(3) 被算了 2 次，F(2) 被算了 3 次）

2. 最优子结构
   全局最优解包含子问题的最优解
   （要算 F(n)，必须先算 F(n-1) 和 F(n-2)）

为什么 DP 能解决问题？
因为我们只算每个子问题一次，然后保存结果！

DP vs 普通递归：

普通递归：
F(5) → F(4) → F(3) → F(2) → F(1) → 返回
              ↑
        这里 F(3) 已经被算过了，但又算了一遍！

DP（记忆化）：
F(5) → F(4) → F(3) → F(2) → F(1)
                  ↓
            保存 F(3) 的结果，下次直接用

1.3 什么是"最优子结构"？（面试必问）

面试官追问："什么是最优子结构？为什么重要？"

最优子结构的意思是：

问题的最优解，可以由子问题的最优解推导出来。

反例：最短路径 vs 最长路径

问题：从 A 到 D 的最短路径
路径：A → B → C → D

如果我知道从 A 到 C 的最短路径，
再加上 C → D，就得到了 A 到 D 的最短路径。

这就是最优子结构！

但是！如果问最长路径呢？
A → B → C → D 可能不是最长的
A → B → D 可能更长！

所以最长路径问题没有最优子结构，
不能用 DP 解（但可以用记忆化搜索）。

1.4 DP 的两种实现方式

1. 自顶向下（记忆化递归）
   - 从大问题开始，递归到小问题
   - 缓存计算结果，避免重复计算
   - 代码直观，但可能有栈溢出问题

2. 自底向上（填表法）
   - 从小问题开始，逐步填表到大问题
   - 用循环替代递归，没有栈溢出
   - 需要确定填表顺序

两者是等价的！选择看场景。

---

二、如何解决 DP 问题？（方法论）

2.1 四步法（解决任何 DP 问题）

面试官追问："拿到一个问题，怎么判断能不能用 DP？"

解决 DP 问题的四步法：

Step 1: 定义状态
         dp[i] 是什么意思？

Step 2: 找到状态转移
         dp[i] 怎么由 dp[i-1], dp[i-2]... 推导？

Step 3: 确定初始状态
         dp[0]、dp[1] 是什么？

Step 4: 确定计算顺序
         从小到大还是其他顺序？

2.2 实例：最大子数组和

面试官追问："最大子数组和怎么用 DP 解？"

问题：找连续子数组的最大和
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

直觉解法：枚举所有子数组，O(n²) 或 O(n³)

DP 解法：

Step 1: 定义状态
         dp[i] = 以第 i 个元素结尾的最大子数组和

Step 2: 状态转移
         dp[i] = max(nums[i], dp[i-1] + nums[i])

         解释：要么从 nums[i] 重新开始，
              要么把 nums[i] 接在 dp[i-1] 后面

Step 3: 初始状态
         dp[0] = nums[0]

Step 4: 计算顺序
         从 i=1 到 i=n-1，顺序计算

验证：
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

dp[0] = -2
dp[1] = max(1, -2+1) = 1         ← 重新开始
dp[2] = max(-3, 1+(-3)) = -2    ← 接前面的
dp[3] = max(4, -2+4) = 4         ← 重新开始
dp[4] = max(-1, 4+(-1)) = 3     ← 接前面的
dp[5] = max(2, 3+2) = 5
dp[6] = max(1, 5+1) = 6
dp[7] = max(-5, 6+(-5)) = 1
dp[8] = max(4, 1+4) = 5

答案：max(dp) = 6

2.3 状态定义的技巧（面试核心）

面试官追问："我怎么知道该怎么定义状态？"

好的状态定义特点：
1. 含义清晰
2. 能推导出状态转移
3. 能覆盖所有情况

常见的状态定义模式：

1. "以 i 结尾..."
   dp[i] = 以第 i 个元素结尾的某种最优解
   （前面例子：最大子数组和）

2. "前 i 个..."
   dp[i] = 前 i 个元素的最优解
   （例子：打家劫舍）

3. "从 i 到 j..."
   dp[i][j] = 从 i 到 j 的最优解
   （例子：区间 DP）

关键是：状态定义决定了转移方程！

---

三、经典 DP 问题讲解

3.1 爬楼梯（入门级）

考察点：最简单的 DP，理解状态转移

问题：爬 n 层楼梯，每次可以爬 1 或 2 层，有多少种爬法？

Step 1: 定义状态
         dp[i] = 爬到第 i 层的最少步数方法数

Step 2: 状态转移
         dp[i] = dp[i-1] + dp[i-2]
         要到第 i 层，要么从 i-1 爬 1 步，要么从 i-2 爬 2 步

Step 3: 初始状态
         dp[1] = 1
         dp[2] = 2

Step 4: 计算顺序
         从小到大

dp: 1, 2, 3, 5, 8, 13, 21...
这不就是斐波那契数列吗！

面试追问：为什么是斐波那契？
回答：因为每次选择 1 或 2，正好是斐波那契定义

3.2 打家劫舍（理解"前 i 个"的状态）

考察点：状态定义的进阶

问题：偷窃一条街的房子，不能偷相邻两家，最大收益

nums = [2, 7, 9, 3, 1]

直觉：选或不选，怎么选？

Step 1: 定义状态
         dp[i] = 偷窃前 i 家（0...i-1）的最大收益

Step 2: 状态转移
         dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
         解释：
         - 不偷第 i-1 家：dp[i-1]
         - 偷第 i-1 家：dp[i-2] + nums[i-1]（必须跳过 i-2）

Step 3: 初始状态
         dp[0] = 0（没有房子，收益 0）
         dp[1] = nums[0]（只有第一间）

Step 4: 计算顺序
         从小到大

验证：
nums = [2, 7, 9, 3, 1]

dp[0] = 0
dp[1] = 2
dp[2] = max(2, 0+7) = 7
dp[3] = max(7, 2+9) = 11
dp[4] = max(11, 7+3) = 11
dp[5] = max(11, 11+1) = 12

答案：12

3.3 最长递增子序列（理解 O(n²) 到 O(n log n)）

考察点：状态定义 + 二分优化

问题：找最长递增子序列的长度

nums = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 101] 或 [2, 3, 7, 18]，长度是 4

Step 1: 定义状态
         dp[i] = 以 nums[i] 结尾的 LIS 长度

Step 2: 状态转移
         dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]

Step 3: 初始状态
         dp[i] = 1（每个元素自己就是一个长度为 1 的 LIS）

Step 4: 计算顺序
         i 从 0 到 n-1

时间复杂度：O(n²)

面试追问：怎么优化到 O(n log n)？
回答：维护一个有序数组，用二分查找

维护数组 d：
d[k] = 长度为 k 的递增子序列的最小结尾元素

遍历 nums：
- 用二分查找找第一个 >= nums[i] 的位置
- 替换或追加

最终 d 的长度就是 LIS 长度

---

四、DP 的本质（面试总结）

4.1 什么时候用 DP？

满足两个条件：
1. 有重叠子问题
2. 有最优子结构

判断方法：
- 如果暴力搜索有重复计算 → 可能是 DP
- 如果问题可以"分解"成子问题 → 可能是 DP

4.2 DP vs 其他算法

┌─────────────────────────────────────────────────┐
│                    算法选择                       │
├─────────────────────────────────────────────────┤
│                                                  │
│  问题特点          推荐算法                        │
│  ─────────────────────────────────────────────  │
│  子问题不重叠        分治 / 递归                   │
│  子问题重叠 + 最优子结构  DP                       │
│  需要遍历所有情况    暴力搜索 / 回溯               │
│  问题有单调性        贪心 / 二分                   │
│                                                  │
└─────────────────────────────────────────────────┘

4.3 面试高频追问

---

五、面试总结

DP 问题的核心套路

1. 判断能不能用 DP
   - 有重叠子问题？
   - 有最优子结构？

2. 定义状态
   - dp[i] 或 dp[i][j] 是什么意思？
   - 能覆盖所有情况吗？

3. 找状态转移
   - dp[i] 怎么由小问题的 dp 推导？
   - 写出来，画个图验证

4. 确定初始状态
   - dp[0]、dp[1] 是什么？
   - 边界条件处理

5. 确定计算顺序
   - 从小到大？
   - 从大到小？
   - 填表顺序要对

6. 考虑空间优化
   - 真的需要完整数组吗？
   - 只保留最近几个状态？

面试能加分的回答

1. 能说出 DP 的本质
   "DP 就是用空间换时间，把重叠子问题的结果缓存起来"

2. 能判断什么时候用 DP
   "如果问题能分解成子问题，且子问题会重复，就用 DP"

3. 能快速找到状态转移
   "问自己：假设已经知道 dp[i-1]，怎么求 dp[i]？"

4. 能解释为什么 DP 能工作
   "因为有最优子结构，全局最优包含局部最优"

---

相关题目

• LeetCode 70 - 爬楼梯 - DP 入门
• LeetCode 198 - 打家劫舍 - 状态定义
• LeetCode 300 - 最长递增子序列 - O(n²) 到 O(n log n)
• LeetCode 53 - 最大子数组和 - 一维 DP