问题的最优解包含子问题的最优解。例如：
递归求解时反复出现相同子问题，DP通过记忆化避免重复计算。
dp[i][c] = max(dp[i-1][c], dp[i-1][c-w_i] + v_i)
# Python 简洁实现 (空间优化)
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for c in range(capacity, weights[i]-1, -1):
dp[c] = max(dp[c], dp[c-weights[i]] + values[i])
return dp[capacity]
⏱ O(n·C) 空间 O(C)
dp[c] = max(dp[c], dp[c-w_i] + v_i) (正序遍历)
# 完全背包 (Python)
def unbounded_knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for c in range(weights[i], capacity+1):
dp[c] = max(dp[c], dp[c-weights[i]] + values[i])
return dp[capacity]
♻️ 物品无限，正序更新
状态： dp[mask][v] 表示从起点0出发，经过集合 mask 中的城市，最后到达城市 v 的最短路径长度。
递推：
dp[mask][v] = min(
dp[mask\{v}][u] + dist[u][v]
for u in mask\{v}
)
初始化 dp[1<<0][0] = 0，最终答案 min(dp[(1<
⏱ O(n²·2ⁿ) 空间 O(n·2ⁿ)
子集 {0,1,3} 状态示例
dp[i][j] = max( dp[i-1][j-1] + match, dp[i-1][j] + gap, dp[i][j-1] + gap )
# 全局对齐 (简化)
def align(x, y, match=2, gap=-1):
n, m = len(x), len(y)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1): dp[i][0] = i * gap
for j in range(m+1): dp[0][j] = j * gap
for i in range(1, n+1):
for j in range(1, m+1):
score = match if x[i-1]==y[j-1] else -1
dp[i][j] = max(dp[i-1][j-1]+score,
dp[i-1][j]+gap, dp[i][j-1]+gap)
return dp[n][m]
| _ | A | G | C | |
|---|---|---|---|---|
| _ | 0 | -1 | -2 | -3 |
| A | -1 | 2 | 1 | 0 |
| C | -2 | 1 | 1 | 3 |
🔹 回溯可得最优对齐：A-C 与 AGC 的比对
⏱ O(n·m) 空间 O(n·m) / 可优化至 O(min(n,m))
| 问题 | 状态维度 | 递推特点 | 时间复杂度 | 空间优化 |
|---|---|---|---|---|
| 0-1背包 | dp[i][c] | 逆序容量 | O(n·C) | 滚动数组 O(C) |
| 完全背包 | dp[c] | 正序容量 | O(n·C) | O(C) |
| TSP (Held-Karp) | dp[mask][v] | 子集枚举 | O(n²·2ⁿ) | O(n·2ⁿ) |
| 序列对齐 | dp[i][j] | 三种转移 | O(n·m) | O(min(n,m)) |