1. 动态规划的核心思想
1.1 DP 的本质
最优子结构：问题的最优解包含子问题的最优解。
重叠子问题：递归解法中会反复求解相同的子问题。
状态转移：用已解决的子问题推导更大问题的解。
DP 解题三步曲：
1. 定义状态 dp[i] 或 dp[i][j]：子问题的解
2. 找出状态转移方程：dp[i] = f(dp[i-1], dp[i-2], ...)
3. 确定初始条件和遍历顺序
1.2 DP vs 递归 vs 贪心
| 特性 | 递归 | 动态规划 | 贪心 |
|---|---|---|---|
| 子问题重叠 | 重复计算 | 记忆化/递推，不重复 | 不重复 |
| 最优子结构 | 不一定 | 必须满足 | 必须满足 |
| 全局最优 | 不一定 | 保证 | 不一定保证 |
| 时间 | 指数级（无优化） | 多项式 | 多项式 |
2. 经典一维 DP
2.1 斐波那契数列
# 暴力递归：O(2^n)
def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
# 记忆化搜索：O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# 递推（空间优化）：O(n) 时间，O(1) 空间
def fib_dp(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
2.2 爬楼梯问题
def climb_stairs(n):
"""
状态：dp[i] = 爬到第 i 阶的方法数
转移：dp[i] = dp[i-1] + dp[i-2]（最后一步跨1阶或2阶）
""
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]
2.3 最大子数组和（Kadane 算法）
def max_subarray(nums):
"""
状态：dp[i] = 以 nums[i] 结尾的最大子数组和
转移：dp[i] = max(nums[i], dp[i-1] + nums[i])
空间优化：只保留前一个状态
"""
if not nums:
return 0
curr_max = global_max = nums[0]
for i in range(1, len(nums)):
curr_max = max(nums[i], curr_max + nums[i])
global_max = max(global_max, curr_max)
return global_max
3. 经典二维 DP
3.1 最长公共子序列（LCS）
def lcs(text1, text2):
"""
dp[i][j] = text1[:i] 和 text2[:j] 的最长公共子序列长度
转移：
text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
3.2 最长递增子序列（LIS）
import bisect
def length_of_lis(nums):
"""
O(n log n) 解法：tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
"""
tails = []
for num in nums:
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
tails.append(num)
else:
tails[idx] = num
return len(tails)
# O(n²) 经典 DP
def length_of_lis_dp(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) if dp else 0
3.3 编辑距离
def min_distance(word1, word2):
"""
dp[i][j] = word1[:i] 转成 word2[:j] 的最小编辑距离
操作：插入、删除、替换
"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # 全部删除
for j in range(n + 1):
dp[0][j] = j # 全部插入
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1, # 删除
dp[i][j - 1] + 1, # 插入
dp[i - 1][j - 1] + 1 # 替换
)
return dp[m][n]
4. 背包问题家族
4.1 0-1 背包
def knapsack_01(weights, values, capacity):
"""
每件物品只能选一次
dp[i][w] = 前 i 件物品，容量 w 时的最大价值
"""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i - 1][w], # 不选
dp[i - 1][w - weights[i - 1]] + values[i - 1] # 选
)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
# 一维空间优化（逆序遍历）
def knapsack_01_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
4.2 完全背包
def knapsack_unbounded(weights, values, capacity):
"""
每件物品可以选无限次
正序遍历（因为可以重复选）
"""
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(weights[i], capacity + 1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
4.3 多重背包
def knapsack_multi(weights, values, counts, capacity):
"""
每件物品有数量限制
二进制优化：将 k 拆分为 1, 2, 4, ..., k-2^m+1
"""
items = []
for i in range(len(weights)):
k = counts[i]
w, v = weights[i], values[i]
power = 1
while k > 0:
take = min(power, k)
items.append((w * take, v * take))
k -= take
power *= 2
# 转化为 0-1 背包
dp = [0] * (capacity + 1)
for w, v in items:
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
5. 区间 DP
5.1 矩阵链乘法
def matrix_chain_order(dims):
"""
dims[i] 和 dims[i+1] 是第 i 个矩阵的行列
dp[i][j] = 矩阵 i 到 j 的最小乘法次数
"""
n = len(dims) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1): # 区间长度
for i in range(n - length + 1): # 起始点
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n - 1]
5.2 回文子串
def longest_palindrome(s):
"""
dp[i][j] = s[i:j+1] 是否为回文
"""
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True # 单个字符是回文
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
if length == 2:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and length > max_len:
start, max_len = i, length
return s[start:start + max_len]
6. 状态压缩 DP
def tsp(dist):
"""
旅行商问题状态压缩
dp[mask][i] = 已访问 mask 中的城市，当前在城市 i 的最短距离
mask 用二进制表示访问集合
"""
n = len(dist)
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 从城市 0 出发
for mask in range(1 << n):
for i in range(n):
if not (mask & (1 << i)):
continue
if dp[mask][i] == float('inf'):
continue
for j in range(n):
if mask & (1 << j):
continue
new_mask = mask | (1 << j)
dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j])
# 回到起点
final_mask = (1 << n) - 1
return min(dp[final_mask][i] + dist[i][0] for i in range(1, n))
状态压缩 DP 适用于 n ≤ 20 的集合问题，时间复杂度 O(n² × 2ⁿ)。
7. DP 优化技巧
7.1 空间优化：滚动数组
二维 DP 中若当前行只依赖上一行，可将空间从 O(n²) 降为 O(n)：
# 最长公共子序列 — 空间优化版
def lcs_optimized(text1, text2):
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev, curr = curr, prev # 滚动交换
return prev[n]
7.2 单调队列优化
多重背包中，若状态转移形如 dp[i] = max(dp[i-k*w] + k*v)，可用单调队列将 O(n×W×C) 优化至 O(n×W)：
from collections import deque
def knapsack_mono_queue(weights, values, counts, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
w, v, c = weights[i], values[i], counts[i]
for r in range(w):
# 对模 w 同余类分别维护单调队列
q = deque()
for k in range((capacity - r) // w + 1):
idx = r + k * w
val = dp[idx] - k * v
while q and q[-1][1] <= val:
q.pop()
q.append((k, val))
while q and q[0][0] < k - c:
q.popleft()
dp[idx] = q[0][1] + k * v
return dp[capacity]
7.3 斜率优化（Convex Hull Trick）
当转移方程可改写为 dp[i] = min(dp[j] + (i-j)²) 这类形式时，维护下凸包可将 O(n²) 优化至 O(n)。
8. DP 常见误区与调试
| 误区 | 表现 | 解决方案 |
|---|---|---|
| 状态定义不清晰 | 不知道 dp[i] 代表什么 | 回归问题，写出文字定义 |
| 遍历顺序错误 | 0-1 背包正序遍历，导致重复使用 | 画依赖图，确认方向 |
| 边界条件遗漏 | dp[0] 未初始化或初始值错误 | 用小规模样例手动推演 |
| 状态压缩后索引越界 | mask 位运算出错 | assert mask < (1«n) |
| 浮点精度问题 | TSP 最优解与次优解差 < 1e-6 | 变更状态定义，放大单位 |
调试技巧：对 n ≤ 10 的小规模数据，打印完整 dp 表格，与暴力解法对比。
9. DP 应用场景扩展
| 场景 | DP 类型 | 实际应用 |
|---|---|---|
| 文本 Diff | 编辑距离 / LCS | Git diff、版本控制、代码合并 |
| 语音识别 | Viterbi（基于 DP） | 隐马尔可夫模型最优路径解码 |
| 计算生物学 | 序列比对 | DNA 相似度分析（Needleman-Wunsch） |
| 资源调度 | 背包 / 线性 DP | 云服务器资源分配、广告预算分配 |
| 金融量化 | 期望 DP | 期权定价、最优交易策略 |
| 游戏 AI | 状态压缩 DP | 棋类局面评估、回合制最优策略 |
10. DP 复杂度速查表
| 问题 | 状态数 | 转移代价 | 总复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 斐波那契 | O(n) | O(1) | O(n) | O(1) 优化后 |
| 0-1 背包 | O(n×W) | O(1) | O(n×W) | O(W) 优化后 |
| 完全背包 | O(n×W) | O(1) | O(n×W) | O(W) |
| 编辑距离 | O(m×n) | O(1) | O(m×n) | O(min(m,n)) |
| LCS | O(m×n) | O(1) | O(m×n) | O(min(m,n)) |
| 矩阵链乘 | O(n²) | O(n) | O(n³) | O(n²) |
| TSP | O(n×2ⁿ) | O(n) | O(n²×2ⁿ) | O(n×2ⁿ) |
| 树形 DP | O(n×k) | O(k) | O(n×k²) | O(n×k) |
7. DP 应用总结
| 问题类型 | 状态定义 | 典型例题 |
|---|---|---|
| 线性 DP | dp[i] | 爬楼梯、最大子数组、打家劫舍 |
| 二维 DP | dp[i][j] | LCS、LIS、编辑距离 |
| 背包 DP | dp[w] 或 dp[i][w] | 0-1背包、完全背包、多重背包 |
| 区间 DP | dp[i][j] | 矩阵链、回文子串、石子合并 |
| 状态压缩 | dp[mask][i] | TSP、状态压缩博弈 |
| 树形 DP | dp[node][k] | 树上最大独立集、树直径 |
| 数位 DP | dp[pos][tight] | 统计满足条件的数字个数 |
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。