题目
Given a non-empty array 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.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
题意
给定一个整型数组，求该数组能否分为两个子数组，要求他们的和相等
题解
首先求总和，如果总和为奇数，则返回False,因为奇数不能平分为两个整数。接着定义一个dp数组,dp[i]表示 数组中存在子数组和为i，即dp[i]=true;而我们的目标是求出i=sum/2是否满足；即target=sum/2，求dp[target]是否为true；对于每一个数num，由于都是正整数，所以只会越加越大，所有每取一个数，加上去的数就会落与[num,target]之间，所以在这个范围内，如果存在一个数j，且dp[j-num]为true，说明dp[j]为true,即前面的元素能构成和为j-num的子数组,此时在加上num就等于j,dp[j]就为true；所以有状态转移方程dp[j] = dp[j] || dp[j-num]；这里还要或操作是防止之前赋值为true的情况被后面的重新赋值为False;最后不要忘记dp[0]为true;
代码
func canPartition(nums []int) bool {
sum:=0
for _,n:=range nums{
sum+=n
}
if sum&1==1{
return false
}
target := sum>>1
dp := make([]bool,target+1)
dp[0]=true
for _,num:=range nums{
for i:=target;i>=num;i--{
dp[i] = dp[i]||dp[i-num]
}
}
return dp[target]
}
总结
这道题对于我来说算是比较难的，看了dp的解法也是思考了很久，不太理解这道理里面的思路。现在大致的思路就是，首先目标target为我们求和的最大值，所以每一个范围最大都是到target，然后再[num,target]这个范围依次取出一个数来，是因为此时的前面的元素和（可能是前面所有元素的和，也可能是前面某些元素的和，甚至为0）加上当前的num，是会落在这个范围内，所以如果存在dp[j-num]为true,说明此时dp[j]为可能求得的和。依照这个思路遍历就可以求得最终的结果
