416. 分割等和子集

一 题目：

二 思路：

• 背包问题
• 状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
• 状态转移方程：很多时候，状态转移方程思考的角度是「分类讨论」，对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。
  不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
  选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
• 状态转移方程：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
• 一般写出状态转移方程以后，就需要考虑初始化条件。这里dp[0][0]为false，拿0号物品放0重量袋子肯定放不了
• dp[i][j] 是否i个数里任选若干个数字可以组成j
  可能情况：
  • 当前物品nums[i]不选,看看能否组成j，即判断dp[i-1][j]=true;
  • 当前物品nums[i]本身就等于j, 即判断nums[i]=j
  • 当前物品nums[i]要选才能组成j,也就是其他物品要组成j-nums[i],即判断 dp[i-1][j-nums[i]]=true,但是这里要注意j需要大于nums[i]
• 思路来源

三 代码：

class Solution {
    public boolean canPartition(int[] nums) {
        //数组的和
        int sum=0,max=0;
        for (int num : nums) {
            sum+=num;
            max=Math.max(num,max);
        }

        //目标值，这里其实就转换为是否能从nums里任选n个数字，其和恰好为target了
        int target=sum/2;

        //如果是奇数或者数组里有数字大于其一半的值就直接返回
        if ((sum&1)==1||max>target ){
            return false;
        }

        int length = nums.length;
        //dp[i][j] 是否i个数里任选若干个数字可以组成j
        //可能情况：
        //  当前物品nums[i]不选,看看能否组成j，即判断dp[i-1][j]=true;
        //  当前物品nums[i]本身就等于j, 即判断nums[i]=j
        //  当前物品nums[i]要选才能组成j,也就是其他物品要组成j-nums[i],即判断 dp[i-1][j-nums[i]]=true,但是这里要注意j需要大于nums[i]
        boolean[][] dp=new boolean[length][target+1];
        //初始化(组成重量为0的数)
        dp[0][0]=false;

        for (int i = 1; i <length; i++) {
            for (int j = 0; j <= target; j++) {
                //先按第一种情况进行赋值，后面再修改
                dp[i][j]=dp[i-1][j];

                if (nums[i]==j){
                    dp[i][j]=true;
                    continue;
                }

                if (j>nums[i]){
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
                }
            }
        }

        return dp[length-1][target];
    }
}