每日OJ题_01背包②_力扣416. 分割等和子集

目录

力扣416. 分割等和子集

问题解析

解析代码

滚动数组优化代码

---

力扣416. 分割等和子集

416. 分割等和子集

难度 中等

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

示例 1：

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

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

class Solution {
public:
    bool canPartition(vector<int>& nums) {
 
    }
};

---

问题解析

先思考能不能将问题转化成自己熟悉的题型：

如果数组能够被分成两个相同元素之和相同的子集，那么原数组必须有下面几个性质：

• 所有元素之和应该是一个偶数。
• 数组中最大的元素应该小于所有元素总和的一半；
• 挑选一些数，这些数的总和应该等于数组总和的一半。

        根据前两个性质可以提前判断数组能够被划分。根据最后一个性质，可以发现问题能转化成01背包的模型：

• 数组中的元素只能选择一次。
• 每个元素面临被选择或者不被选择的处境。
• 选出来的元素总和要等于所有元素总和的一半。

        其中，数组内的元素就是物品，总和就是背包。那么我们就可以用背包模型的分析方式，来处理这道题。01背包模板中，要记住的是分析问题的模式。用这种分析问题的模式来解决问题。

---

以某个位置为结尾，结合题目要求，定义一个状态表示：

dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能否凑成总和为 j 这个数。

状态转移方程：

线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论：

不选择 nums[i] ：那么是否能够凑成总和为 j ，就要看在前 i - 1 个元素中 选，能否凑成总和为 j。根据状态表示，此时 dp[i][j] = dp[i - 1][j] ; 。

选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是小于等于 j 。 因为如果这个元素都比要凑成的总和大，那选择它就没有意义。那么是否能够凑成总和 为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据状态表示，此时 dp[i][j] = dp[i - 1][j - nums[i]] ;（nums[i] <=  j）。

        综上，两种情况下只要有⼀种能够凑成总和为 j ，那么这个状态就是 true 。因此，状态转移方程为： if(nums[i - 1] <= j) dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] ; else dp[i][j] = dp[i - 1][j] ;

---

初始化：多加一行一列，方便初始化，第一行表示不选择任何元素，要凑成目标和 j 。只有当目标和为 0 的时候才能做到，因此第一行仅需初始化第一个元素 dp[0][0] = true ; 第一列表示凑成目标和 j = 0，什么都不选即可，所以第一列全为 true，因此初始化时把整个表初始化成 false，再把第一列初始化成 true。

填表顺序：根据状态转移方程，需要从上往下填写每一行，每一个的顺序是任意的。

返回值：根据状态表示，返回 dp[n][target] 的值。 其中 n 表示数组的大小， target 表示要凑成的目标和。

---

解析代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto& e : nums)
        {
            sum += e;
        }
        if(sum % 2 == 1) // 如果是奇数直接返回false
            return false;
        
        int target = sum / 2, n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        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(nums[i - 1] <= j)
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][target];
    }
};

---

滚动数组优化代码

背包问题基本上都是利用滚动数组来做空间上的优化：（时间也有常数的优化）

1. 利用滚动数组优化。
2. 直接在原始代码上修改。

在01背包问题中，优化的结果为：

1. 删掉所有的横坐标。
2. 修改一下 j 的遍历顺序。

（滚动数组优化代码只需能在原代码上修改就行，不用考虑什么状态表示）

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto& e : nums)
        {
            sum += e;
        }
        if(sum % 2 == 1) // 如果是奇数直接返回false
            return false;
        
        int target = sum / 2, n = nums.size();
        vector<bool> dp(target + 1, false); // 滚动数组优化
        dp[0] = true;
 
        for(int i = 1; i <= n; ++i)
        {
            for(int j = target; nums[i - 1] <= j; --j)
            {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        return dp[target];
    }
};