LeetCode 416. 分割等和子集

1、题目

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];
    }
}