C++刷leetcode（416. 分割等和子集）【动态规划】

糖逗

题目描述：

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //计算累加和
        int len = nums.size();
        vector<int>store(len+1, 0);
        store[0] = 0;
        store[1] = nums[0];
        //预判
        for(int i = 2; i <= len; i++){
            store[i] = store[i-1] + nums[i-1];
        }
        if(store[len] % 2 != 0)return false;
        vector<vector<bool> >dp(len, vector<bool>(store[len] + 1, false));
        //初始化
        for(int i = 0; i < len; i++){
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        //动态规划
        for(int i = 1; i < len; i++){
            for(int j = 0; j <= store[i]; j++){
                if(dp[i-1][j] == true){
                    //不加当前
                    dp[i][j] = true;
                    //加当前
                    dp[i][j + nums[i]] = true;
                    if(j + nums[i] == store[len] / 2)return true;
                    //cout << i << " " << j << "--"<< i << " " << j + nums[i] << "--";
                }
            }
            //cout << endl;
        }
        return false;
    }
};