19、递归与动态规划：背包问题的递归解法与DP优化
背包问题，可以说是递归和动态规划的经典入门题。我当年刚学C语言时，第一次看到这个题目，脑子里全是「这也能递归？」的疑问。后来在项目中做资源分配优化时，才发现这玩意儿真能派上用场。
今天咱们就把背包问题拆开揉碎了讲。从最朴素的递归开始，一步步优化到动态规划。你跟着我的思路走，保证能搞明白。
19.1 背包问题是什么？
先说说问题本身。你有一个背包，容量有限。面前有一堆物品，每个物品有自己的重量和价值。你的目标很简单：在不超过背包容量的前提下，让装进去的物品总价值最大。
举个例子：
物品： 重量 价值
物品0： 1 15
物品1： 3 20
物品2： 4 30
背包容量：4你想想看，怎么选？可以选物品0+物品1，总重量4，价值35。也可以只选物品2，重量4，价值30。显然前者更优。
这个问题难在哪？难在「选或不选」的组合爆炸。3个物品还好说，要是30个、300个呢？暴力枚举根本不可能。
19.2 递归解法：先暴力再优化
我个人习惯，遇到这种问题先写递归。递归的好处是思路清晰，代码短，容易验证正确性。
递归的核心思路是什么？对于每个物品，我们只有两个选择：拿或者不拿。
- 如果不拿，问题变成：在剩余物品中，用同样的容量，求最大价值。
- 如果拿，问题变成：在剩余物品中，用减去当前物品重量后的容量，求最大价值，再加上当前物品的价值。
你看，这不就是递归吗？
int knapsack(int w[], int v[], int n, int capacity) {
// 没有物品了，或者容量为0
if (n == 0 || capacity == 0) {
return 0;
}
// 当前物品太重，装不下
if (w[n-1] > capacity) {
return knapsack(w, v, n-1, capacity);
}
// 选或不选，取最大值
int not_take = knapsack(w, v, n-1, capacity);
int take = v[n-1] + knapsack(w, v, n-1, capacity - w[n-1]);
return (not_take > take) ? not_take : take;
}代码很简洁，对吧？但问题来了——效率极低。
为什么会这样？因为大量子问题被重复计算了。比如你选了物品0没选物品1，和没选物品0选了物品1，最后可能到达同一个状态——剩余容量相同，剩余物品相同。但递归会分别计算两次。
19.3 记忆化搜索：递归的救星
我曾经在项目中做缓存优化时，就遇到过类似的重复计算问题。解决办法很简单：把算过的结果存起来。
这就是记忆化搜索，也叫「带备忘录的递归」。
#define MAX_N 100
#define MAX_C 1000
int memo[MAX_N][MAX_C];
int knapsack_memo(int w[], int v[], int n, int capacity) {
if (n == 0 || capacity == 0) {
return 0;
}
// 查备忘录
if (memo[n][capacity] != -1) {
return memo[n][capacity];
}
int result;
if (w[n-1] > capacity) {
result = knapsack_memo(w, v, n-1, capacity);
} else {
int not_take = knapsack_memo(w, v, n-1, capacity);
int take = v[n-1] + knapsack_memo(w, v, n-1, capacity - w[n-1]);
result = (not_take > take) ? not_take : take;
}
// 存入备忘录
memo[n][capacity] = result;
return result;
}嗯，这里要注意：memo数组要初始化为-1，因为价值可能是0。用-1表示「还没算过」。
这个优化后，时间复杂度降到了 O(n * capacity)。n=30，capacity=1000，也就3万次计算，跟之前的10亿次比，天壤之别。
19.4 动态规划：自底向上的艺术
记忆化搜索虽然好，但递归本身有栈开销。我建议你进一步改成迭代的动态规划。
说白了，动态规划就是「从最小的子问题开始，一步步往上推」。
我们定义一个二维数组 dp[i][j]，表示：前i个物品，容量为j时，能获得的最大价值。
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])翻译成人话：
- 不拿第i个物品：价值 = dp[i-1][j]
- 拿第i个物品：价值 = dp[i-1][j - w[i-1]] + v[i-1]
- 两者取大
int knapsack_dp(int w[], int v[], int n, int capacity) {
int dp[n+1][capacity+1];
// 初始化：0个物品，价值为0
for (int j = 0; j <= capacity; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= capacity; j++) {
if (w[i-1] > j) {
dp[i][j] = dp[i-1][j];
} else {
int not_take = dp[i-1][j];
int take = v[i-1] + dp[i-1][j - w[i-1]];
dp[i][j] = (not_take > take) ? not_take : take;
}
}
}
return dp[n][capacity];
}19.5 空间优化：一维数组就够了
你看上面的代码，用了二维数组。但仔细想想，dp[i][j]只依赖dp[i-1][...]，也就是上一行的数据。那我们能不能只用一行？
可以。但要注意遍历顺序。
如果从左往右遍历，更新dp[j]时，dp[j - w[i-1]]可能已经被当前物品更新过了，相当于一个物品被用了多次。这就不对了。
所以必须从右往左遍历。
int knapsack_dp_1d(int w[], int v[], int n, int capacity) {
int dp[capacity+1];
// 初始化
for (int j = 0; j <= capacity; j++) {
dp[j] = 0;
}
for (int i = 0; i < n; i++) {
// 从右往左遍历，保证每个物品只用一次
for (int j = capacity; j >= w[i]; j--) {
int not_take = dp[j];
int take = v[i] + dp[j - w[i]];
dp[j] = (not_take > take) ? not_take : take;
}
}
return dp[capacity];
}19.6 三种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素递归 | O(2^n) | O(n) | n很小（≤20） |
| 记忆化搜索 | O(n*C) | O(n*C) | 理解递归到DP的过渡 |
| 动态规划（二维） | O(n*C) | O(n*C) | 需要回溯具体方案 |
| 动态规划（一维） | O(n*C) | O(C) | 只求最大值，空间敏感 |
19.7 知识体系图
下面这张图帮你理清背包问题的知识脉络：
19.8 避坑指南
最后分享几个我踩过的坑：
- 数组越界：dp数组的容量维度要+1，因为下标从0到capacity。我曾经忘了这个，debug了一下午。
- 初始化遗漏：记忆化搜索的memo数组一定要初始化为-1。用0初始化的话，价值为0的情况会被误认为「没算过」。
- 遍历顺序搞反：一维DP从右往左遍历，这是0-1背包的关键。从左往右就变成完全背包了，结果完全不一样。
- 递归深度：n很大的时候，递归可能导致栈溢出。我建议生产环境直接用迭代DP，别用递归。
背包问题看似简单，但它是理解动态规划的绝佳入口。你把这个搞透了，后面遇到什么最长公共子序列、最短路径，思路都是一样的——找到状态，写出转移方程，然后优化。
好了，今天就到这里。代码你多敲几遍，尤其是从递归到DP的演变过程，每一步都要亲手实现。光看是学不会的。