动态规划(Dynamic Programming,DP)是面试中区分度最高的算法题型,也是很多人的噩梦。其实它的核心只有一句话:把大问题拆成重叠的小问题,记住小问题的答案,避免重复计算。本文用一个套路带你入门。
1. 从斐波那契说起
还记得递归篇里指数级的朴素斐波那契吗?它的低效根源是重叠子问题:同一个子问题被反复计算。解决办法是把结果存下来——这就是 DP 的雏形。
# 自底向上:从最小子问题开始,一步步推到大问题
def fib_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_dp(50)) # 12586269025,瞬间完成2. DP 五步法
- 定义状态:dp[i] 表示什么?最重要的一步。
- 状态转移方程:dp[i] 如何由更小的状态算出。
- 初始条件:dp[0]、dp[1] 等边界值。
- 遍历顺序:保证算 dp[i] 时依赖项已就绪。
- 优化(可选):滚动数组压缩空间。
3. 例题:爬楼梯
一次可以爬 1 或 2 阶,爬到 n 阶有几种方法?到第 i 阶,只能从 i-1 阶跨 1 步或从 i-2 阶跨 2 步过来,所以 dp[i] = dp[i-1] + dp[i-2]。
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(climb_stairs(3)) # 3: (1,1,1) (1,2) (2,1)看出来了吗?它和斐波那契几乎一样——识别题目背后的数学模型,是 DP 的关键能力。
4. 二维 DP:路径问题
进阶题:m×n 网格从左上走到右下,每次只能向右或向下,有多少条路径?状态变为二维:dp[i][j] = dp[i-1][j] + dp[i][j-1]。
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
print(unique_paths(3, 3)) # 6
print(unique_paths(3, 7)) # 28若网格中有障碍物,把障碍处的 dp 值设为 0 即可——理解后 LeetCode 63 题一分钟能写出来。
5. 背包问题:DP 的经典试金石
0-1 背包:容量 W,每个物品有重量 w[i] 与价值 v[i],求能装下的最大价值。定义 dp[j] 为容量 j 时的最大价值,对每个物品倒序更新容量,保证每个物品只用一次:
def knapsack(W, weights, values):
dp = [0] * (W + 1)
for w, v in zip(weights, values):
for j in range(W, w - 1, -1): # 倒序,防止重复取
dp[j] = max(dp[j], dp[j - w] + v)
return dp[W]
W = 5
print(knapsack(W, [2, 1, 3], [4, 2, 3])) # 6: 选 1 号 + 2 号倒序遍历是 0-1 背包的命门:正序会让同一物品被用两次,退化成完全背包。
6. 新手最容易踩的坑
- 状态定义含糊:写代码前先一句话说清 dp[i] 的含义。
- 忘记初始化:dp[0]、dp[1] 不设对,后面全错。
- 循环顺序错:依赖还没算出来就用了,结果随机。
💡 学习建议:DP 靠"量的积累 + 套路总结"。按"一维 → 二维 → 背包 → 区间"的顺序刷 30 道经典题,每道按五步法写注释,比盲目刷 200 道有效。