动态规划 解题模板

适用场景

最优化问题（最大/最小/方案数/可行性），有重叠子问题和最优子结构

通用推导路径

 
暴力递归 → 记忆化搜索 → 自底向上 DP → 空间优化
 

常见类型模板

线性 DP（斐波那契类）

 
# 70爬楼梯: dp[i] = dp[i-1] + dp[i-2]
 
a, b = 1, 1
 
for _ in range(n-1):
 
    a, b = b, a + b
 

网格 DP

 
# 空间优化：一维滚动
 
for i in range(m):
 
    dp[0] += grid[i][0]  # 第一列
 
    for j in range(1, n):
 
        dp[j] = grid[i][j] + min(dp[j], dp[j-1])
 

背包 DP

 
# 0/1 背包（每个物品最多一次）：内层倒序
 
for num in nums:  # 物品
 
    for j in range(target, num-1, -1):
 
        dp[j] = dp[j] or dp[j-num]
 
# 完全背包（无限次）：内层正序
 
for coin in coins:
 
    for j in range(coin, amount+1):
 
        dp[j] = min(dp[j], dp[j-coin] + 1)
 
# 背包排列数（顺序有关）：外层金额，内层物品
 
for j in range(1, target+1):
 
    for num in nums:
 
        if j >= num: dp[j] += dp[j-num]
 

区间 DP

 
# 按区间长度从小到大递推
 
for length in range(2, n+1):
 
    for i in range(n-length+1):
 
        j = i + length - 1
 
        # dp[i][j] = f(dp[i][k], dp[k+1][j])
 

树形 DP

 
# 后序遍历
 
def dfs(node):
 
    if not node: return (0, 0)
 
    left = dfs(node.left)
 
    right = dfs(node.right)
 
    rob = node.val + left[1] + right[1]
 
    skip = max(left) + max(right)
 
    return (rob, skip)
 

复杂度总结

类型	时间	空间	典型题
线性	O(n)	O(1)	70、198、746
背包	O(n×target)	O(target)	416、322、494、139
LCS/编辑距离	O(m×n)	O(n)	1143、72
区间	O(n²)	O(n²)	5、647
树形	O(n)	O(h)	337、124、543
状态机	O(n)	O(1)	121、309

关键要点

• 状态定义是最关键的一步

• 转移方程不要漏边界条件

• 初始化 dp[0] 和数组越界检查

• 空间优化版本要讲清为什么能工作

• 背包问题注意遍历顺序

→ 查看该分类题目：LeetCode学习路线图 > 十三、动态规划

---

相似题对比

易混题对	关键区别	解法差异
70爬楼梯 vs 746最小花费	计数 vs 最小花费	加法 vs 取min+cost
62不同路径 vs 63不同路径II	无障碍 vs 有障碍	障碍处dp=0
198打家劫舍 vs 213打家劫舍II	直线 vs 环形	拆环成两趟直线
322零钱兑换 vs 518零钱兑换II	最少硬币数 vs 方案数	min(..+1) vs sum(…)
1143最长公共子序列 vs 718最长重复子数组	子序列可不连续 vs 子数组必须连续	LCS vs 连续匹配(不等时归零)
416分割等和子集 vs 494目标和	是否存在(或) vs 方案数(加)	0/1背包 dp[j]=dp[j]
300最长递增子序列 vs 674最长连续递增序列	不要求连续 vs 必须连续	DP O(n²) 或 patience O(n log n) vs 一次遍历 O(n)

---

测试用例模板

 
# 基础功能
 
assert climbStairs(3) == 3
 
assert climbStairs(4) == 5
 
# 边界
 
assert climbStairs(1) == 1               # n=1
 
assert climbStairs(2) == 2               # n=2
 
# 特殊
 
assert coinChange([1], 0) == 0           # amount=0
 
assert coinChange([2], 3) == -1          # 无解
 
assert coinChange([1,2,5], 11) == 3      # 普通情况
 

---

关联题型

关联题型	常见结合方式	典型题目
贪心	贪心可看作DP简化版	55跳跃游戏, 122买卖股票
回溯	回溯→记忆化→DP	322零钱兑换, 139单词拆分
树形DP	树上的DP	337打家劫舍III, 124最大和