C++动态规划实战：01背包问题从入门到精通（附LeetCode真题解析）

很多刚开始接触算法，尤其是准备技术面试的朋友，一听到“动态规划”四个字就有点发怵，总觉得它深不可测，是区分“普通程序员”和“算法高手”的一道坎。而01背包问题，恰恰是动态规划领域最经典、也最“友好”的入门导师。它没有复杂的图论结构，没有烧脑的数学公式，核心思想就一句话：面对一堆物品，每个只能拿或不拿，如何在有限的背包容量下，拿到最大的总价值？

这个看似简单的模型，却能衍生出无数变种，成为解决LeetCode上许多中等甚至困难题目的万能钥匙。比如，给你一个数组，问能否将其分割成两个和相等的子集（LeetCode 416）；或者，给你一堆石头，每次碰撞后剩下重量差，问最后剩下的石头最小可能是多重（LeetCode 1049）。这些问题，本质上都是01背包的“换装”游戏。

今天，我们不打算照本宣科地复述教科书定义，而是换一条路：从你最可能遇到的LeetCode真题出发，反向拆解，带你一步步“发明”出01背包的解法。我们会用C++手把手实现两种核心代码（二维数组和空间优化的滚动数组），并深入探讨如何将千变万化的实际问题，精准地抽象成背包模型。当你读完这篇文章，再回头看那些题目，你会发现它们不再是孤立的难题，而是一个个熟悉的“老朋友”。

1. 从LeetCode真题反向理解：为什么是背包问题？

让我们暂时忘掉“背包”、“容量”、“价值”这些术语。先看一道实实在在的LeetCode题目：416. 分割等和子集。

题目描述：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]。

你的第一反应是什么？回溯？枚举所有子集？数组长度稍微一大，这种暴力方法的时间复杂度就会指数级爆炸，完全不可行。这时，动态规划的思路就该登场了。

关键转化步骤：

1. 计算总和：首先，如果整个数组的和 sum 是奇数，那绝对不可能平分成两个整数和，直接返回 false。
2. 定义目标：如果 sum 是偶数，那么我们的目标就变成了：能否从数组中选出一部分数，使得它们的和恰好等于 target = sum / 2。
3. 建立背包模型：
   • 背包容量：就是我们的目标 target。
   • 物品：数组中的每个数字 nums[i]。
   • 物品重量：数字本身的值 nums[i]。
   • 物品价值：在这个问题里，我们只关心“能否凑出某个和”，不关心价值最大化。但为了套用背包框架，我们可以把价值也看作 nums[i]，而我们的目标就是让价值恰好等于容量 target。

看，一个分割子集的问题，瞬间变成了：“有一个容量为 target 的背包，有一堆重量和价值都是 nums[i] 的物品，每种物品只有一个。请问能否恰好装满这个背包？” 这就是一个标准的01背包问题，只不过问题的答案从“最大价值”变成了“能否恰好装满”。

为了更直观，我们用一个简单的例子来推演一下思维过程：

假设 nums = [1, 2, 3, 6]，总和为12，target = 6。 我们能否从 [1,2,3,6] 中选一些数，和为6？

• 选6本身，可以。
• 选1+2+3，也可以。

这个过程，就像在决定每个数字“放”还是“不放”进和为6的“背包”里。这就是01背包“选或不选”的核心决策。

注意：这里引出了01背包问题中一个至关重要的细分点——“恰好装满”与“不超过容量”。在分割等和子集问题中，我们要求的是“恰好装满”。这会影响我们初始化动态规划数组的方式，后文会详细展开。

2. 动态规划的核心：状态定义与转移方程

通过上一节，我们把一个具体问题转化成了背包模型。现在，我们需要用动态规划的“语言”将这个模型表述出来。动态规划的本质是用空间换时间，通过记录并复用子问题的解来避免重复计算。

2.1 状态定义

我们定义一個二维数组 dp：

• dp[i][j] 表示：考虑前 i 个物品（nums[0] 到 nums[i-1]），在背包容量恰好为 j 的情况下，所能获得的最大价值（在这个问题里，最大价值就是能凑出的最大和）。
• 由于是“恰好装满”，如果无法用前 i 个物品凑出容量 j，我们将其值设为一个特殊标记（比如 -1 或 INT_MIN），表示不可行状态。

为什么是“前i个物品”和“容量j”？ 这是一种非常经典的“阶段”与“状态”的划分。“前i个物品”代表了决策的阶段，我们正在处理第 i 个物品。“容量j”代表了在当前阶段下，背包剩余的空间状态。通过遍历所有 i 和 j，我们就能系统地探索所有可能的决策组合。

2.2 状态转移方程

这是动态规划最精妙的部分。对于第 i 个物品（对应 nums[i-1]，因为我们的 i 从1开始计数），面对容量 j 的背包，我们只有两种选择：

1. 不放入背包：那么当前的最大价值，就等于只考虑前 i-1 个物品、容量为 j 时的最大价值。即 dp[i][j] = dp[i-1][j]。
2. 放入背包：前提是背包容量 j 必须大于等于这个物品的重量 nums[i-1]。如果放入，那么背包剩余容量变为 j - nums[i-1]，此时的最大价值就是“前 i-1 个物品在剩余容量下的最大价值”加上当前物品的价值 nums[i-1]。即 dp[i][j] = dp[i-1][j - nums[i-1]] + nums[i-1]。

我们的目标是最大化价值（在这个问题里是最大化凑出的和，但不超过 j），所以最终的转移方程是两者取最大值：

if (j >= nums[i-1]) {
    dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i-1]] + nums[i-1]);
} else {
    dp[i][j] = dp[i-1][j]; // 放不下，只能继承之前的状态
}

一个重要的理解：dp[i-1][j - nums[i-1]] 这个状态必须是一个“有效”状态，即前 i-1 个物品能够恰好凑出和 j - nums[i-1]。如果它是无效的（例如被初始化为-1），那么即使当前物品能放下，这个选择也是无效的。在“恰好装满”的问题中，这一点尤其关键。

2.3 初始化

初始化是保证递推正确的基石。

• dp[0][0] = 0：考虑0个物品，要凑出总和为0，是可行的（什么都不选），且最大价值为0。
• dp[0][j] = -1 (j > 0)：考虑0个物品，要凑出任何正数的和，都是不可能的。我们用-1表示这种不可能状态。
• dp[i][0] = 0：对于任何数量的物品，要凑出总和为0，都是可行的（什么都不选）。

将上述思路整合，我们可以写出解决 LeetCode 416. 分割等和子集 的二维DP解法：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        int n = nums.size();
        
        // dp[i][j]: 前i个数字能否恰好组成和为j
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        // 初始化：和为0总是可以达成（不选任何数）
        for (int i = 0; i <= n; ++i) dp[i][0] = true;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= target; ++j) {
                if (j < nums[i-1]) {
                    // 当前数字大于目标和，不能选
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 不选当前数字 或 选当前数字
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }
};

注意：这里我们将 dp 数组定义为 bool 类型，因为问题只关心“能否”凑出，不关心最大价值。状态转移方程也相应地从 max 变成了逻辑或 ||。

3. 空间优化：滚动数组的艺术

上面的二维DP解法清晰易懂，但空间复杂度是 O(n * target)。观察状态转移方程 dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]]，你会发现，计算第 i 行的数据时，只依赖于第 i-1 行的数据。这意味着我们不需要保存整个二维表格，只需要保存“上一行”的数据即可。

这就是 “滚动数组” 优化技术。我们可以将二维数组压缩成一维数组 dp[j]，其含义是：对于当前正在考虑的物品，容量为 j 的背包能否被恰好装满。

关键点：内层循环必须倒序遍历（从 target 到 nums[i-1]）！

为什么？因为 dp[j] 依赖于 dp[j - nums[i-1]]，而这个值是“上一轮”计算出来的。如果我们正序遍历，在计算 dp[j] 时，dp[j - nums[i-1]] 可能已经被当前轮次的更新覆盖了，这就相当于同一个物品被使用了多次，变成了“完全背包”问题，违背了01背包“每个物品只能用一次”的规则。

倒序遍历保证了在更新 dp[j] 时，dp[j - nums[i-1]] 还是上一轮（即考虑前 i-1 个物品时）的值。

优化后的一维DP代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false; // 快速判断奇偶
        int target = sum >> 1; // 除以2
        vector<bool> dp(target + 1, false);
        dp[0] = true; // 容量为0时，总可以达成
        
        for (int num : nums) {
            // 必须从后往前遍历！
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j - num];
            }
            // 一个小优化：如果提前找到了target，可以直接返回
            if (dp[target]) return true;
        }
        return dp[target];
    }
};

空间复杂度从 O(n*target) 降到了 O(target)，这是一个巨大的提升，尤其是在 target 很大但 n 也很大的场景下。这种优化思路在01背包及其变种问题中几乎成为标配。

为了帮助你理解二维和一维DP的对应关系，我们来看一个状态更新的对比表格。假设 nums = [2, 3, 5], target = 7。

步骤 (物品)	一维数组 dp (容量0~7) 的更新过程 (倒序)	对应的二维数组 dp[i][j] 行
初始	[T, F, F, F, F, F, F, F]	dp[0][j]
处理物品 2	j=7~2: dp[j] = dp[j] || dp[j-2] 结果: [T, F, T, F, F, F, F, F]	dp[1][j]
处理物品 3	j=7~3: dp[j] = dp[j] || dp[j-3] 结果: [T, F, T, T, F, T, F, F]	dp[2][j]
处理物品 5	j=7~5: dp[j] = dp[j] || dp[j-5] 最终: [T, F, T, T, F, T, F, T]	dp[3][j]

表格说明：T代表true，F代表false。最终dp[7]=T，说明可以凑出和为7。可以看到，一维数组在每一轮迭代后，其状态完全等价于二维数组的对应行。

4. 举一反三：识别与抽象背包模型

掌握了01背包的标准解法后，真正的挑战在于如何识别出那些“披着羊皮”的背包问题。LeetCode上有很多题目，初看与背包无关，但经过巧妙转化，都能用01背包的思路高效解决。

4.1 经典变种一：LeetCode 1049. 最后一块石头的重量 II

题目：有一堆石头，用整数数组 stones 表示，其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y - x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

问题转化： 每次碰撞，实际上是让两块石头的重量相互抵消。我们的目标是让最后剩下的石头重量最小。这等价于：将这堆石头分成两堆，使得两堆石头的总重量尽可能接近。设总重量为 sum，两堆重量分别为 A 和 B（A <= B，且 A + B = sum）。碰撞后剩余的重量就是 B - A。我们要最小化 B - A，也就是最大化 A，但 A 不能超过 sum / 2（因为 A <= B）。

看，问题又回来了！在总容量为 sum/2 的背包中，尽可能多地装入石头（物品重量=石头重量，价值=石头重量），求能装下的最大重量 A。那么最终答案就是 (sum - A) - A = sum - 2 * A。

C++实现（一维DP）：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2; // 向下取整，A最大可能的值
        vector<int> dp(target + 1, 0); // dp[j]：容量为j的背包能装的最大重量
        
        for (int stone : stones) {
            for (int j = target; j >= stone; --j) {
                dp[j] = max(dp[j], dp[j - stone] + stone);
            }
        }
        // dp[target] 就是我们能凑出的、不超过target的最大重量A
        return sum - 2 * dp[target];
    }
};

4.2 经典变种二：LeetCode 494. 目标和

题目：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个 表达式 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

问题转化： 设添加 + 的数字之和为 pos，添加 - 的数字之和为 neg。则有：

1. pos - neg = target
2. pos + neg = sum (数组总和)

将两式相加可得：2 * pos = target + sum => pos = (target + sum) / 2。

因此，问题转化为：从 nums 中选取若干个数，使得它们的和恰好等于 (target + sum) / 2，问有多少种不同的选取方法。这又是一个01背包问题，但这次我们求的是方案数。

状态定义调整： dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法。

状态转移方程调整： 当考虑数字 num 时，如果选择它来凑容量 j，那么凑出 j 的方法数，就加上凑出 j - num 的方法数。所以转移方程为： dp[j] += dp[j - num] （需保证 j >= num）

初始化： dp[0] = 1，因为凑出和为0（不选任何数）有一种方法。

C++实现：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 如果目标绝对值大于总和，或者 (target+sum) 为奇数，则无解
        if (abs(target) > sum || (target + sum) % 2 != 0) return 0;
        int bagSize = (target + sum) / 2;
        // 防止bagSize为负数，取绝对值？不，这里bagSize应该是非负的，如果计算为负说明问题无解。
        if (bagSize < 0) return 0;
        
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        
        for (int num : nums) {
            for (int j = bagSize; j >= num; --j) {
                dp[j] += dp[j - num];
            }
        }
        return dp[bagSize];
    }
};

4.3 抽象模型识别要点

通过以上例子，我们可以总结出将实际问题抽象为01背包模型的几个关键步骤：

1. 识别“容量”和“物品”：找到问题中那个有限的、约束性的量（如总和的一半、背包容量、表达式目标值的一半），它就是“背包容量”。找到那些你可以选择“取”或“不取”的个体，它们就是“物品”。
2. 定义“重量”和“价值”：“重量”通常是物品消耗“容量”的量度（如数字本身的值、石头的重量）。“价值”是你需要最大化、最小化或计算方案数的目标（如数字的和、方案数量）。有时“重量”和“价值”是相同的（如分割等和子集）。
3. 确定是“最大价值”还是“方案数”：这是决定 dp 数组含义和转移方程的关键。求最大/最小值，用 max/min；求方案总数，用累加 +=。
4. 判断是“恰好”还是“不超过”：这决定了初始化和状态转移时的边界条件处理。“恰好装满”通常需要将不可行状态初始化为一个特殊值（如 -INF 或 false），而“不超过”则可以将所有状态初始化为可行状态的基础值（如0）。

为了帮助你快速判断，这里有一个常见问题类型的对照表：

实际问题描述	背包容量	物品	物品重量	物品价值	目标	对应LeetCode题
能否分割等和子集	数组和的一半	数组中的数字	数字值	数字值	价值是否恰好等于容量	416
最后一块石头的最小重量	总重的一半	石头	石头重量	石头重量	在不超过容量的前提下，最大化价值	1049
目标和的方法数	(target+sum)/2	数组中的数字	数字值	不适用	填满背包的方案数	494
零钱兑换II (硬币数量无限)	总金额	硬币面额	面额	不适用	填满背包的方案数	518 (此为完全背包)

注意：零钱兑换II属于“完全背包”问题，因为硬币数量无限。其内层循环是正序遍历，与01背包的倒序遍历不同。

5. 避坑指南与性能优化

理论懂了，代码也会写了，但在实际动手和面试中，依然可能踩坑。下面分享几个我调试代码和面试别人时经常遇到的问题。

5.1 初始化陷阱

这是最容易出错的地方之一，尤其是涉及“恰好装满”的问题。

• “恰好装满”的最大价值问题：例如，求在恰好装满背包容量 V 时的最大价值。如果不可能恰好装满，则返回一个特定值（如-1）。
  • 错误初始化：dp[0...V] = 0。这表示在任何容量下，不装物品的价值是0，但这样最终 dp[V] 可能来自“没有恰好装满”的状态。
  • 正确初始化：dp[0] = 0，dp[1...V] = -INF（用一个很小的负数，如 INT_MIN）。这样，任何从无效状态转移来的结果依然是无效的（max 操作不会选中它）。只有真正能恰好装满的状态，其值才会是非负数。

// 示例：求恰好装满背包的最大价值
vector<int> dp(V + 1, INT_MIN);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
    for (int j = V; j >= weight[i]; --j) {
        if (dp[j - weight[i]] != INT_MIN) { // 确保是从有效状态转移而来
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}
int result = (dp[V] == INT_MIN) ? -1 : dp[V]; // 处理无法恰好装满的情况

5.2 遍历顺序陷阱

一维DP中，内层循环必须倒序，这是01背包的铁律。正序遍历会导致物品被重复计算，变成完全背包问题。我建议在写代码时，把 for (int j = V; j >= weight[i]; --j) 作为模板记下来。

5.3 输入数据范围与边界检查

在解题平台或面试中，务必关注数据范围。

• 数组长度 n 和背包容量 V：这决定了你的DP数组大小。如果 V 非常大（例如10^9），那么 O(n*V) 的DP会超时或超内存，可能需要换思路（如折半搜索）。
• 数值大小：在计算 target = (target + sum) / 2 这类式子时，要小心整数溢出。在C++中，可以使用 long long 类型进行中间计算。
• 负数和零：有些变种问题可能包含非正整数。在“目标和”问题中，我们假设了 (target+sum) 为非负偶数。如果存在负数，可能需要使用偏移量或将DP数组定义为 map。

5.4 空间与时间优化技巧

1. 一维DP优先：在绝大多数情况下，一维滚动数组解法是首选，除非你需要回溯具体方案（这时需要完整的二维DP表）。
2. 提前剪枝：像分割等和子集问题，在一维DP循环中，如果发现 dp[target] 已经为 true，可以立即返回，节省不必要的计算。
3. 物品预处理：如果物品重量很大，但价值很低，或者反过来，可以考虑对循环顺序或数据结构做优化，但01背包的经典DP解法通常已经足够高效。
4. 理解时间复杂度：O(n * V)，其中 n 是物品数量，V 是背包容量。这在 n 和 V 都在几百到几千的范围内是完全可以接受的。如果 V 过大，则需要思考问题是否真的需要精确解，或者是否有其他特性（如重量种类很少）可以利用。

最后，分享一个我在面试中喜欢问的思考题：“如果问题要求输出具体是哪几个物品构成了最优解，而不仅仅是最大价值或能否装满，该如何修改算法？” 这需要你在DP过程中记录额外的路径信息，通常是用一个独立的 path 数组或回溯二维DP表来完成。这不仅能考察对01背包本质的理解，还能延伸到动态规划的一个常见扩展——构造最优解。