1、题目
image.png
2、分析
这个题目还是比较难理解的。
难点在于状态转移如何推算。即如何通过之间的状态，推断出dp[i][j]。
dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
dp[i - 1][j - nums[i - 1]] ： 这个是第nums[i]个元素，加到和中，刚好等于j
dp[i - 1][j]：这个是第nums[i]个元素，不加到和中。dp[i][j] 继承dp[i - 1][j] 的结果。
参考链接分析：https://labuladong.github.io/zgnb/3/16/24/
3、代码
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int n : nums) sum += n;
if(sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[][] dp = new boolean[n + 1][sum + 1];
for(int i = 0; i <= n; i++){
dp[i][0] = true;
}
for(int j = 1; j <= sum; j++){
dp[0][j] = false;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sum; j++){
if(j - nums[i -1] < 0){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
}
}
}
return dp[n][sum];
}
}
