LeetCode #416：Partition Equal Subset Sum(分割等和子集)

题目描述

本题是比较经典的一个 01 背包问题，把数组和的一半看作背包容量，看数组元素是否能放满背包即可。

使用二维数组进行 dp 的解法如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        int sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i ++) {
            sum += nums[i];
        }

        if(sum % 2 == 1) return false; //和为奇数时不可能分割

        vector< vector<int> > f(n, vector<int>(sum / 2 + 1, -1));

        for(int j = 0; j <= sum / 2; j ++) {
            if(j >= nums[0]) f[0][j] = nums[0];
        }

        for(int i = 1; i < n; i ++) {
            for(int j = 0; j <= sum / 2; j ++) {
                f[i][j] = f[i - 1][j];
                if(j - nums[i] >= 0) //当前剩余空间是否够够放第i个数
                    f[i][j] = max(f[i][j], f[i - 1][j - nums[i]] + nums[i]); //权重和价值都是nums[i]
            }
        }

        return f[n - 1][sum / 2] == sum / 2;
    }
};

我们知道 01 背包问题的状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，即本题中为 f[i][j] = max(f[i - 1][j], f[i - 1][j - nums[i]] + nums[i])。由于 f[i][j] 的结果只依赖于上一行，故我们可以把 dp 数组压缩为 2*背包容量 来优化空间复杂度：原 dp 数组的偶数行映射到新 dp 数组的第 0 行、原 dp 数组的奇数行映射到新 dp 数组的第 1 行。

dp 数组优化成两行的版本如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        int sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i ++) {
            sum += nums[i];
        }

        if(sum % 2 == 1) return false;

        vector< vector<int> > f(2, vector<int>(sum / 2 + 1, -1)); //将dp数组修改为两行 

        for(int j = 0; j <= sum / 2; j ++) {
            if(j >= nums[0]) f[0][j] = nums[0];
        }

        for(int i = 1; i < n; i ++) {
            for(int j = 0; j <= sum / 2; j ++) {
                f[i % 2][j] = f[(i - 1) % 2][j]; //涉及到访问第i行和第i-1行时需要i % 2
                if(j - nums[i] >= 0) //当前剩余空间是否够够放第i个数
                    f[i % 2][j] = max(f[i % 2][j], f[(i - 1) % 2][j - nums[i]] + nums[i]); //权重和价值都是nums[i]
            }
        }

        return f[(n - 1) % 2][sum / 2] == sum / 2; //最终结果取n-1行也要取余
    }
};

这个版本已经能处理足够大的数据量了。当然我们要进一步压缩 dp 数组到一维也是可以的，不过要换成从后向前遍历数组——因为后面的值是依赖前面的，若从前往后遍历，后面的值还没等到更新，前面依赖的值就先被更新了。

最终一维 dp 的代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        int sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i ++) {
            sum += nums[i];
        }

        if(sum % 2 == 1) return false;

        vector<int> f(sum / 2 + 1, -1); //将dp数组修改为一维 

        for(int j = 0; j <= sum / 2; j ++) {
            if(j >= nums[0]) f[j] = nums[0];
        }

        for(int i = 1; i < n; i ++) { //从后向前遍历dp数组
            for(int j = sum / 2; j >= nums[i]; j --) { //将当前剩余空间是否够够放第i个数的判断放在第二层for循环上
                f[j] = max(f[j], f[j - nums[i]] + nums[i]); //权重和价值都是nums[i]
            }
        }

        return f[sum / 2] == sum / 2;
    }
};