代码随想录链接:代码随想录
思路:
可以将数组分为两部分，其中一部分记作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整数数组默认初始值为0if (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];}
}
