C++动态规划：从LeetCode真题入手，彻底搞懂01背包问题

1. 01背包问题核心思想解析

01背包问题是动态规划领域的经典案例，它完美展示了如何将复杂问题分解为可管理的子问题。想象你有一个容量有限的背包和一堆物品，每个物品都有其重量和价值。你的目标是在不超过背包容量的前提下，选择物品组合使得总价值最大化。

这个问题的核心在于每个物品只有两种选择：放入背包（1）或不放入（0），因此得名"01背包"。关键在于理解状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

这个方程表示：

• 不选当前物品时，价值保持前i-1个物品的最优解（dp[i-1][j]）
• 选择当前物品时，价值为前i-1个物品在剩余容量下的最优解加上当前物品价值（dp[i-1][j-w[i]] + v[i]）

关键点：

• 二维数组dp[i][j]表示考虑前i个物品，背包容量为j时的最大价值
• 需要特别注意边界条件：当j < w[i]时，只能选择不放入

2. LeetCode实战：分割等和子集

让我们通过LeetCode 416题《分割等和子集》来实践01背包的应用。题目要求判断一个数组是否能被分成两个和相等的子集。

2.1 问题转化技巧

这道题可以巧妙转化为01背包问题：

1. 计算数组总和sum
2. 如果sum为奇数，直接返回false
3. 问题转化为：是否存在子集的和等于sum/2

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    // 后续01背包解法...
}

2.2 完整实现与优化

标准二维DP解法：

vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
    for (int j = 0; 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]];
        }
    }
}

空间优化的一维DP解法（推荐）：

vector<bool> dp(target+1, false);
dp[0] = true;
for (int num : nums) {
    for (int j = target; j >= num; j--) {
        dp[j] = dp[j] || dp[j - num];
    }
}
return dp[target];

注意：内层循环必须逆序，避免重复计算。这是01背包空间优化的关键技巧。

3. 进阶应用：最后一块石头的重量II

LeetCode 1049题《最后一块石头的重量II》展示了01背包的另一种变形应用。题目要求每次选两块石头相撞，最终剩下最小的可能重量。

3.1 问题转化思路

这道题的解法非常巧妙：

1. 将石头分成两堆，使两堆的重量尽可能接近
2. 最终结果就是两堆重量的差值
3. 问题转化为：背包容量为总重量一半时的最大装载量

int lastStoneWeightII(vector<int>& stones) {
    int sum = accumulate(stones.begin(), stones.end(), 0);
    int target = sum / 2;
    vector<int> dp(target + 1, 0);
    
    for (int stone : stones) {
        for (int j = target; j >= stone; j--) {
            dp[j] = max(dp[j], dp[j - stone] + stone);
        }
    }
    
    return sum - 2 * dp[target];
}

3.2 关键实现细节

1. 初始化dp数组大小为target+1，初始值为0
2. 外层循环遍历每个石头
3. 内层逆序遍历容量，确保每个石头只被使用一次
4. 最终结果为sum - 2*dp[target]，因为一堆是dp[target]，另一堆是sum-dp[target]

4. 01背包的优化技巧与变种

4.1 空间优化：滚动数组

原始的二维DP会消耗O(nW)空间，通过观察状态转移方程可以发现，当前状态只与前一行有关，因此可以优化为一维数组：

vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) {  // 注意逆序
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

为什么必须逆序？

• 正序会导致物品被重复计算（变成了完全背包问题）
• 逆序保证了每个物品只被考虑一次

4.2 常见变种问题

变种类型	问题特点	解决方法调整
恰好装满	要求背包必须装满	初始化时dp[0]=0，其他为-∞
方案计数	求达到最大价值的方案数	修改状态转移为累加计数
多维限制	多个限制条件（如重量+体积）	使用多维dp数组
物品分组	物品间有依赖关系	增加状态维度表示选择情况

4.3 初始化细节对比

不同的初始化方式会导致不同的求解目标：

// 常规初始化（不要求装满）
vector<int> dp(W + 1, 0);

// 要求恰好装满的初始化
vector<int> dp(W + 1, INT_MIN);
dp[0] = 0;

5. 从理论到实践：代码模板与调试技巧

5.1 通用01背包模板

int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    
    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

5.2 调试与验证技巧

1. 打印DP表：对于小规模问题，打印整个DP数组验证
2. 边界测试：空数组、单个物品、容量为0等特殊情况
3. 跟踪选择：如果需要记录选择了哪些物品，可以额外维护一个选择数组

// 打印DP表（二维版本）
void printDPTable(const vector<vector<int>>& dp) {
    for (const auto& row : dp) {
        for (int val : row) {
            cout << setw(4) << val;
        }
        cout << endl;
    }
}

5.3 性能优化建议

1. 提前终止：当dp[target]达到目标时可提前结束
2. 物品排序：按单位价值排序可能提高效率（但不改变最坏复杂度）
3. 分支限界：对于大规模问题，可结合贪心算法进行剪枝

6. 复杂场景下的应用扩展

01背包的思想可以扩展到许多看似无关的问题上。例如：

应用案例1：目标和的组合数（LeetCode 494）

• 问题：给非负整数数组和目标S，通过+/-使表达式结果为S的组合数
• 转化：将问题视为找出和为(S+sum)/2的子集数

应用案例2：字符串分割（LeetCode 139）

• 问题：判断字符串能否被字典中的单词分割
• 转化：将字典视为物品，字符串位置视为背包容量

应用案例3：买卖股票的最佳时机（带手续费）

• 问题：多次买卖股票，每次交易需手续费
• 转化：将持有/不持有股票视为两种状态

这些扩展应用展示了动态规划思想的强大灵活性。关键在于识别问题中的"选择"和"状态"，然后建立合适的状态转移方程。

在实际面试中，遇到以下特征的问题可考虑01背包思路：

• 问题涉及做出一系列二元选择
• 有明确的容量/资源限制
• 需要最大化某个值或判断可行性

掌握01背包不仅能解决特定问题，更能培养将复杂问题分解为子问题的思维能力，这是算法设计中的核心技能。