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 应用总结
| 问题类型 | 状态定义 | 典型例题 |
|---|---|---|
| 线性 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] | 统计满足条件的数字个数 |
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。