代码随想录链接:代码随想录

思路:

可以将数组分为两部分，其中一部分记作left，其中数字的符号全为+,而另外一部分记作right，其中数字的符号全为-。这里全为-的意思不是真正的符号为-，而表示这一堆数字在计算时取值为负

因此有如下的关系:

left + right = sum,其中sum为数组和

left - right = target，其中target为目标值

可以得出left = (sum + target) / 2

因此原问题转换为在集合nums中找出和为left的组合共有多少种

也就是用nums装满容量为x的背包，有几种方法。这里的x，就是bagSize，也就是我们后面要求的背包容量

方法一:使用二维dp数组求解:

(1).确定dp数组的形式以及对应的含义:

dp[i][j]:使用原始数组下标为[0,i]的元素能够凑满j(包括j)这么大容量的包，有dp[i][j]种方法

其中dp数组的维度大小为N*(left+1)，其中N为原始数组中数据的个数，而left =  (sum + target) / 2

(2).确定递推公式:

对于dp数组中的元素dp[i][j]来说，有两种推导方式:

第一种是不放元素i，此时背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法

第二种是放元素i，此时需要先空出物品i的容量，因此背包容量为(j - 物品i容量)，放满背包有dp[i - 1][j - 物品i容量]种方法

需要注意的是，当j - nums[i]小于零时，表示此时背包无法放入物品i，此时装满背包的方法值 等于不放物品i的装满背包的方法，即：dp[i][j] = dp[i - 1][j]

因此有如下的推导公式:

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

 (3).dp数组的初始化:

由于递推公式需要左上方的元素，因此需要初始化第一行和第一列

dp[0][0]表示装满背包容量为0 的方法数量是1，即 放0件物品，因此dp[0][0] = 1

初始化第一行dp[0][j]:

dp[0][j]表示只放物品0， 把容量为j的背包填满有几种方法

因此:只有背包容量为物品0的容量的时候，方法为1，正好装满。其他情况下，要不是装不满，要不是装不下。所以初始化dp[0][nums[0]] = 1 ，其他均为0

初始化第一列dp[i][0]:

dp[i][0]表示背包容量为0， 放物品0到物品i装满有几种方法。此时由于背包的容量为0，因此只有一种方法，因此第一列全为1

但是如果原始数组中有0元素，此时dp[i][0]应该为2的n次方，其中n为元素[0,i]中0的个数

(4).确定遍历顺序:

遍历顺序一定是从上到下，从左到右

Java代码:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {

        // 01背包应用之“有多少种不同的填满背包最大容量的方法“
        // 易于理解的二维数组解法及详细注释

        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        // 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和
        // 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）
        if(sum < Math.abs(target)){
            return 0;
        }

        // 利用二元一次方程组将left用target和sum表示出来（替换掉right组合），详见代码随想录对此题的分析
        // 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的
        if((sum + target) % 2 != 0) {
            return 0;
        }

        int left = (sum + target) / 2;
        
        // dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数
        int[][] dp = new int[nums.length][left + 1];

        // 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
        // 其他情况dp[0][j] = 0
        // java整数数组默认初始值为0
        if (nums[0] <= left) {
            dp[0][nums[0]] = 1;
        }

        // 初始化最左列（dp[i][0])
        // 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
        // n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）
        int numZeros = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);

        }

        // 递推公式分析：
        // 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
        // nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]
        // 由递推公式可知，先遍历i或j都可
        for(int i = 1; i < nums.length; i++) {
            for(int j = 1; j <= left; j++) {
                if(nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                }
            }
        }


        return dp[nums.length - 1][left];
        
    }
}

方法二:使用一维dp数组

重复利用每一行，就是将二维数组压缩成一行

(1).确定dp数组的含义:

dp[i][j]去掉行的维度，即dp[j]表示填满j(包括j)这么大容积的包，有dp[j]种方法

(2).确定递推公式:

二维DP数组递推公式:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

去掉维度i之后，递推公式:dp[j] = dp[j] + dp[j - nums[i]] ，即：dp[j] += dp[j - nums[i]]

(3).dp数组的初始化:

dp[0] = 1,表示填满容量为0的包共有一种方法

(4).确定遍历顺序:

遍历物品放在外循环，遍历背包在内循环，且内循环倒序(为了保证物品只使用一次)

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];

        //如果target的绝对值大于sum，那么是没有方案的
        if (Math.abs(target) > sum) return 0;
        //如果(target+sum)除以2的余数不为0，也是没有方案的
        if ((target + sum) % 2 == 1) return 0;

        int bagSize = (target + sum) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[bagSize];
    }
}