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]