糖逗 发表于 2021-4-5 13:07:30

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

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

注意:

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

输入:

输出: true

解释: 数组可以分割成 和 .
 

示例 2:

输入:

输出: 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;
      store = nums;
      //预判
      for(int i = 2; i <= len; i++){
            store = store + nums;
      }
      if(store % 2 != 0)return false;
      vector<vector<bool> >dp(len, vector<bool>(store + 1, false));
      //初始化
      for(int i = 0; i < len; i++){
            dp = true;
      }
      dp] = true;
      //动态规划
      for(int i = 1; i < len; i++){
            for(int j = 0; j <= store; j++){
                if(dp == true){
                  //不加当前
                  dp = true;
                  //加当前
                  dp] = true;
                  if(j + nums == store / 2)return true;
                  //cout << i << " " << j << "--"<< i << " " << j + nums << "--";
                }
            }
            //cout << endl;
      }
      return false;
    }
};
页: [1]
查看完整版本: C++刷leetcode(416. 分割等和子集)【动态规划】