动态规划专题：01 背包模型详解与空间优化

2.3 进阶：空间优化（滚动数组）

1. 为什么要逆序？

观察方程：dp[i][j] 只依赖于上一行的 dp[i-1][...]。 如果我们去掉第一维，变成 dp[j]：

• 正序遍历：计算 dp[j] 时，用到的 dp[j-v] 已经是本行更新过的值了（相当于物品 i 被选了多次）。
• 逆序遍历：计算 dp[j] 时，j-v 在 j 的左边，还没被更新，依然是上一行的旧值。这正是我们想要的！

2. 优化后的一维代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, V;
int v[N], w[N];
int dp[N]; // 一维数组

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    // 第一问：不超过 V
    for (int i = 1; i <= n; i++) {
        // 逆序遍历！从 V 到 v[i]
        for (int j = V; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;

    // 第二问：恰好装满 V
    // 初始化：只有容量为 0 时价值为 0，其余为 -INF
    for (int j = 1; j <= V; j++) dp[j] = -0x3f3f3f3f;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            if (dp[j - v[i]] != -0x3f3f3f3f) // 只有前置状态有效才更新
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
    return 0;
}

三、分割等和子集：决策类背包

3.1 题目解析

描述：给你一个正整数数组，能否将其分割成两个子集，使它们的和相等？

示例：[1, 5, 11, 5] -> true (可以分成 {1, 5, 5} 和 {11})

3.2 思路转换

• 转化：这道题等价于——能否从数组中选出一些数，让它们的和恰好等于 sum / 2。
• 映射到背包：
  • 背包容量：sum / 2。
  • 物品：数组里的每个数（体积和价值都是数值本身）。
  • 目标：能否装满？

3.3 朴素二维代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        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，不需要选任何数，天然为 true
        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++) {
                // 不选第 i 个数
                dp[i][j] = dp[i-1][j];
                // 选第 i 个数
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }
};

3.4 空间优化代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true; // 初始化
        
        for (int x : nums) {
            // 逆序遍历，防止重复选择同一个数
            for (int j = target; j >= x; j--) {
                dp[j] = dp[j] || dp[j - x];
            }
        }
        return dp[target];
    }
};

四、目标和：求方案数

4.1 题目解析

描述：每个数字前加 + 或 -，凑成 target。问有多少种方法？

4.2 思路转换

设加正号的数总和为 P，加负号的数总和为 M。 P - M = target，且 P + M = sum。 两式相加得：2P = sum + target ⇒ P = (sum + target) / 2。 问题转化：从数组中选出一些数，让它们的和恰好等于 P，有多少种选法？

4.3 朴素二维代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (abs(target) > sum || (sum + target) % 2 != 0) return 0;
        int bagSize = (sum + target) / 2;
        int n = nums.size();
        // dp[i][j] 前 i 个数凑成和 j 的方案数
        vector<vector<int>> dp(n + 1, vector<int>(bagSize + 1, 0));
        dp[0][0] = 1; // 凑成 0 的方案数为 1 (空集)
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= bagSize; j++) {
                // 不选
                dp[i][j] = dp[i-1][j];
                // 选
                if (j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[n][bagSize];
    }
};

4.4 空间优化代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (abs(target) > sum || (sum + target) % 2 != 0) return 0;
        int bagSize = (sum + target) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        
        for (int x : nums) {
            // 逆序遍历
            for (int j = bagSize; j >= x; j--) {
                dp[j] += dp[j - x];
            }
        }
        return dp[bagSize];
    }
};

五、最后一块石头的重量 II：最小差值

5.1 题目解析

描述：每次选两块石头粉碎，剩下重量差。不断重复，求最后剩下的最小重量。

5.2 思路转换

我们要把石头分成两堆，让它们的重量尽可能接近 sum / 2。 这又是 01 背包：容量为 sum / 2，求能装入的最大重量。

5.3 朴素二维代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int x : stones) sum += x;
        int target = sum / 2;
        int n = stones.size();
        // dp[i][j] 前 i 个石头，容量 j，最大重量
        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= stones[i-1]) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j - stones[i-1]] + stones[i-1]);
                }
            }
        }
        return sum - 2 * dp[n][target];
    }
};

5.4 空间优化代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int x : stones) sum += x;
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        
        for (int x : stones) {
            // 逆序遍历
            for (int j = target; j >= x; j--) {
                dp[j] = max(dp[j], dp[j - x] + x);
            }
        }
        return sum - 2 * dp[target];
    }
};

六、总结：01 背包的灵魂

核心对比卡片：