1、題目
image.png
2塞蹭、分析
這個(gè)題目還是比較難理解的蕴掏。
難點(diǎn)在于狀態(tài)轉(zhuǎn)移如何推算贯底。即如何通過(guò)之間的狀態(tài)，推斷出dp[i][j]写烤。
dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
dp[i - 1][j - nums[i - 1]] ： 這個(gè)是第nums[i]個(gè)元素翼闽，加到和中，剛好等于j
dp[i - 1][j]：這個(gè)是第nums[i]個(gè)元素洲炊，不加到和中感局。dp[i][j] 繼承dp[i - 1][j] 的結(jié)果。
參考鏈接分析：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];
}
}
