木又连续日更第8天(8/100)
木又的第171篇leetcode解题报告
动态规划
类型第16篇解题报告
leetcode第416题:分割等和子集
https://leetcode-cn.com/problems/partition-equal-subset-sum/
【题目】
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
【思路】
这道题还是有难度的,得转换个思维。
两个子集和相等,那么每个子集和为整个数组和的一半。
那么问题就转换为:从数组nums中选择n个数,使得他们的和等于sum(nums) // 2。
我们使用dp[i]表示数组和是否能够得到该值,那么对于数组nums的元素n,只要dp[i]为True,则dp[i+n]为True。
(修改dp数组时,一定从后往前修改,否则会读到“脏数据”)
【代码】
python版本
class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# 2 * 单个数组和,肯定是偶数
target = sum(nums)
if target % 2 == 1:
return False
# 选择n个数,和为target
target = target / 2
dp = [False] * (target + 1)
dp[0] = True
for n in nums:
ls = []
for i in range(len(dp)-1, -1, -1):
# i可以,那么i+n可以
if dp[i] and i + n <= target:
dp[i+n] = True
return dp[-1]
C++版本
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum0 = 0;
for(auto n: nums)
sum0 += n;
// 只有和是偶数,才可能分成两个和相等的数组
if(sum0 % 2 == 1)
return false;
// 选择n个数,和为target
int target = sum0 / 2;
vector<int> dp(target+1, false);
dp[0] = true;
for(auto n: nums){
for(int i = target; i >= 0; i--){
if(dp[i] && i + n <= target)
dp[i+n] = true;
}
}
return dp.back();
}
};