[数据结构与算法]LeetCode动态规划 分割等和子集

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

思路
这道题假如能看出是一道0-1背包问题的话，就很好解决了。题目说需要划分成两个和相等的子集，那么需要满足：
1.每个元素必须被使用且只能被使用一次
2.两个子集的和相等，子集和相加必为偶数

根据子集和相加必为偶数这一点，当nums数组元素和sum是奇数时，直接return false。那么接下来问题就可以转化成能否选取几个物品使其重量和为sum/2的问题。

状态转移方程
dp[i][j] = true, when dp[i-1][j] == true
dp[i][j] = true, when j == nums[i]
dp[i][j] = dp[i-1][j-nums[i]], when j > nums[i]

边界条件
若nums[0] <= sum/2，dp[0][0] = true

注明
为什么此处的初始化不像一般的背包问题那样是个循环呢，我想了一下一般的背包问题是求最大价值和的，所以需要循环一般dp[0][j]记录各自中间值。而本题中不需要记录中间值，只需要判断是true还是false，因此仅需判断dp[0][0]是否为true即可。

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int len = nums.size();
        for(auto num : nums)
        sum += num;
        if(sum % 2) 
        return false;
    
        int bag_size = sum / 2;
        bool dp[205][10005] = {false};
        if(nums[0] <= bag_size)
        dp[0][nums[0]] = true;
        
        for(int i = 1; i < len; i++)
        for(int j = 0; j <= bag_size; j++)
        {
            if(dp[i-1][j] == true)
            dp[i][j] = true;
            else if(j == nums[i])
            dp[i][j] = true;
            else if(j > nums[i])
            dp[i][j] = dp[i-1][j-nums[i]];
        }

        return dp[len-1][bag_size];
    }
};