dp二维数组
优化
dp一维数组
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;//计算总和
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
}
int target = sum >> 1;//将总和分成相等的两份
if(sum % 2 == 1) return false;//总和为奇数不可能分割两个完全一样的数组
int[] dp = new int[target+1];//dp[j]指容量为j时 所容纳的物品最大价值
for(int i = 0; i < nums.length; i++) {//物品
for(int j = target; j >= nums[i]; j--) {//背包
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);//最大价值
if(dp[target] == target) return true;//判断最大价值是否等于背包容量
}
}
return dp[target] == target;
}
}