第四章：动态规划——最优子结构与重叠子问题
动态规划，简称 DP。说实话，这名字起得挺唬人的。我第一次接触时，以为是什么高深莫测的数学理论。后来做项目多了才发现，它本质上就是一种「聪明的穷举」。
你想想看，很多问题我们都能暴力求解，但指数级的时间复杂度谁也扛不住。DP 的核心思路就八个字：记住过去，复用结果。
4.1 最优子结构：大问题拆成小问题
什么叫最优子结构？说白了就是：一个问题的最优解，包含了其子问题的最优解。
举个例子。你要从北京去上海，走一条最短路径。如果这条路径中间经过了济南，那么从北京到济南这一段，也一定是最短的。为什么？因为如果北京到济南有更短的路，那整体路径就能更短，矛盾了。
我在项目中遇到过一个问题：要给一批订单分配生产线。每个订单有利润和工时，总工时有限。这其实就是个背包问题。我当时第一反应就是：先看看子问题怎么解，再拼起来。这就是最优子结构在实战中的直觉。
判断标准：一个问题能否用 DP，先问自己——「去掉最后一步，剩下的部分还是不是同样的问题？」
4.2 重叠子问题：别重复造轮子
有了最优子结构，我们就能递归地解决问题。但递归有个大坑：重复计算。
拿斐波那契数列来说：F(5) = F(4) + F(3)，F(4) = F(3) + F(2)。你看，F(3) 被算了两次。当 n 很大时，这种重复会爆炸。
重叠子问题，就是指不同的子问题会共享相同的更小子问题。DP 的做法很简单：算过一次就存起来，下次直接用。
我曾经接手过一个老代码，里面用递归算组合数，n=30 就跑不动了。我改成 DP 后，n=1000 都秒出。嗯，这就是重叠子问题的威力。
我的习惯：拿到问题先画递归树。如果发现同样的节点出现多次，那 DP 就派上用场了。
4.3 背包问题的 DP 解法
背包问题，是 DP 的经典入门题。我当年面试时，十家公司有八家会考这个。
问题描述：有 N 个物品，每个物品有重量 w[i] 和价值 v[i]。你有一个容量为 C 的背包。问能装下的最大价值是多少？
定义状态：dp[i][j] 表示「前 i 个物品中，选出总重量不超过 j 的最大价值」。
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) // 当 j >= w[i]
dp[i][j] = dp[i-1][j] // 当 j < w[i]说白了就是：对于第 i 个物品，要么不拿（继承上一行的结果），要么拿（腾出重量，加上价值）。
代码实现：
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if j >= weights[i-1]:
dp[i][j] = max(dp[i-1][j],
dp[i-1][j-weights[i-1]] + values[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity]避坑指南：我曾经把物品索引搞混了，导致结果一直不对。记住：代码里的 i-1 对应第 i 个物品，因为 dp 数组多了一行「空物品」的情况。
空间还能优化。你会发现，每次更新只用到了上一行的数据。所以可以压缩成一维数组：
def knapsack_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# 注意：必须倒序遍历，否则会重复使用同一个物品
for j in range(capacity, weights[i]-1, -1):
dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
return dp[capacity]为什么要倒序？因为正序的话，dp[j-weights[i]] 可能已经被当前物品更新过了，相当于一个物品用了多次。这其实是「完全背包」的解法。嗯，这里要注意区分。
4.4 TSP 的 DP 解法：Held-Karp 算法
旅行商问题（TSP）是另一个经典。问题是：给定 n 个城市和两两之间的距离，找一条经过每个城市恰好一次并回到起点的最短路径。
暴力解法是 O(n!)，n=12 就够呛了。Held-Karp 算法用 DP 把它降到 O(n²·2ⁿ)。虽然还是指数级，但 n=20 以内已经可以接受了。
状态定义：dp[mask][i] 表示「已经访问过的城市集合为 mask，当前在 i 城市时，走过的最短路径长度」。
其中 mask 是一个二进制数，第 k 位为 1 表示城市 k 已访问。
转移方程：
dp[mask][i] = min(dp[mask_without_i][j] + dist[j][i])
for all j in mask_without_i代码实现：
def held_karp(dist):
n = len(dist)
# 初始化：从城市0出发
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 只访问了城市0，当前在0
for mask in range(1, 1 << n):
# 只考虑包含城市0的mask
if not (mask & 1):
continue
for i in range(n):
if not (mask & (1 << i)):
continue
# 尝试从j走到i
prev_mask = mask ^ (1 << i)
for j in range(n):
if prev_mask & (1 << j):
dp[mask][i] = min(dp[mask][i],
dp[prev_mask][j] + dist[j][i])
# 回到起点
full_mask = (1 << n) - 1
ans = min(dp[full_mask][i] + dist[i][0] for i in range(1, n))
return ans我的经验：Held-Karp 算法在实际项目中很少直接用于 TSP，因为 n 一大就扛不住。但我用它解决过一个「配送路线规划」问题，n=15，效果很好。关键是学会这种「状态压缩」的思路。
4.5 知识体系总览
下面这张图，是我梳理的本章核心逻辑。你看一遍，应该就能把 DP 的脉络串起来了。
动态规划不是玄学，它是一套可以训练出来的思维方式。我个人习惯是：拿到问题先想能不能拆成子问题，再看子问题有没有重复。两个条件都满足，DP 就是你的菜。
背包问题和 TSP 问题，一个代表「线性 DP」，一个代表「状态压缩 DP」。掌握了这两个，你就掌握了 DP 的半壁江山。
公众号:蓝海资料掘金营，微信deep3321