class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
// 题目已经说非空数组,可以不做非空判断
int sum = 0;
for (int num : nums) {
sum += num;
}
// 特判:如果是奇数,就不符合要求
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
// 创建二维状态数组,行:物品索引,列:容量(包括 0)
int[][] dp = new int[nums.length+1][target+1];
for(int i=1; i<=nums.length;i++){
for(int j=1; j<=target;j++){
if(j<nums[i-1]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
}
}
}
if(target==dp[nums.length][target]) return true;
return false;
}
}
416. 分割等和子集
发布时间 2023-09-25 21:48:20作者: Chenyi_li