本文主要是为了阐述01背包问题涉及的问题点：
1、如何使用二维数组解题？
2、如何优化二维数组，将二维数组转为一维数组？
3、对于01问题，为什么target层循环要倒序？
（PS：对于背包问题不了解的、不知道什么是01背包问题的，可以参考：背包问题总结）
给定一个非负整数数组a1, a2, ..., an, 和一个目标数S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
通过给数组中的元素添加正负符号，使得和为目标数S。
假设数组元素的和为：sum，要添加负号的元素的和为negativeSum，添加正号的元素的和为positiveSum，
那么会有：
sum = positiveSum + negativeSum
S = positiveSum - negativeSum
=》positiveSum = （sum + S）/ 2，也就是说只要能从数组中找到任意个元素的和为（sum + S）/ 2 ，剩下的数设置为负的，则该组合的和就等于S。
故题目可转化为01背包问题：
给定一个非负整数数组a1, a2, ..., an, 和一个目标数target。从数组中选择任意个整数，使得其和等于target，且每个元素最多用一次。求选取的组合个数。
定义一个二维数组 dp 存储组合个数，其中 dp[i][j] 表示在前 i个元素中选择任意个元素的和为 j的组合个数。
对于第 i 个元素num是否被选中，可以分两种情况讨论：
第 i 个元素没有被选中，组合个数就相当于前i-1个数中选择任意个元素的和为 j的组合个数，即dp[i-1][j]。
第 i 个元素被选中，组合个数就相当于前i-1个数中选择任意个元素的和为( j-num)的组合个数，即dp[i-1][j-num]。注意：此种情况需要j>=num
故：
j<num时，dp[i][j] = dp[i-1][j]；j>=num时，dp[i][j] = dp[i-1][j] + dp[i-1][j-num]
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int target = (sum + S) / 2;
int length = nums.length;
int[][] dp = new int[length + 1][target + 1];
// 初始化：前i个数中，选取任意个元素的和为0的组合个数只有一种，就是啥都不选。
for (int i = 0; i <= length; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= length; i++) {
int num = nums[i - 1];
for (int j = 1; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[length][target];
}从上述代码中，可以看出对于dp[i][j]的结果是依赖于dp[i-1]，与其他数据没有任何关系。故在每次计算完前i个数，选择任意个元素和为target的组合数之后，将该结果存起来，用于下一次计算。
故上面的二维数组解法可以优化为：
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int target = (sum + S) / 2;
int length = nums.length;
int[] dp = new int[target + 1];
// 初始化：和为0的组合个数只有一种，就是啥都不选。
dp[0] = 1;
for (int i = 1; i <= length; i++) {
// 记录下前i-1个元素组合的结果数
int[] lastDp = Arrays.copyOf(dp, dp.length);
int num = nums[i - 1];
for (int j = 1; j <= target; j++) {
if (j >= num) {
dp[j] =lastDp[j] + lastDp[j - num];
}else{
dp[j] =lastDp[j];
}
}
}
return dp[target];
}在2中，使用了lastDp来记录前i-1个元素组合的结果数。那么，有没办法可以继续优化空间呢？答案是有的，将target层循环倒序。先给出代码，再讲解为啥需要倒序，倒序和正序有什么区别。
public int findTargetSumWays1(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int target = (sum + S) / 2;
int length = nums.length;
int[] dp = new int[target + 1];
// 初始化：和为0的组合个数只有一种，就是啥都不选。
dp[0] = 1;
for (int i = 1; i <= length; i++) {
int num = nums[i - 1];
for (int j = target; j >= 1; j--) {
if (j >= num) {
dp[j] = dp[j]+dp[j - num];
}else{
dp[j] = dp[j];
}
}
}
return dp[target];
}比对【2、二维数组转为一维数组】中的代码，可以发现，要去除lastDp，只需要将target层循环倒序。这个是为什么呢？
原因就在于：
dp[j] =lastDp[j] + lastDp[j - num]; 即在前i个数中，选取组合的数的和为j的结果等于（lastDp[j] + lastDp[j - num]）；
nums层的每一次循环开始时，dp存储的是前i-1个数的选取的结果。而dp[j]=dp[j]+dp[j-num]，如果计算dp[j]时，dp[j]和dp[j-num]只要取的是前i-1个数选取的结果，那么dp[j]的值就是对的。也就是只要保证在计算dp[j]时，dp[j]和dp[j-num]的值没有被改动过就可以了。
如果采用正序的话，即从dp[1]开始覆盖，直至dp[target]。在计算dp[j]时，dp[j-num]取到的值就不是前(i-1)个数选取的结果了，而是前i个数选取的结果。
故采用倒序，从dp[target]开始计算、开始覆盖，直至dp[1]。计算dp[j]前，dp[j]和dp[j-num]的值都没有变动过。
去除不必要的代码：
public int findTargetSumWays1(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int target = (sum + S) / 2;
int[] dp = new int[target + 1];
// 初始化：和为0的组合个数只有一种，就是啥都不选。
dp[0] = 1;
for (int num : nums) {
for (int j = target; j >= 1; j--) {
if (j >= num) {
dp[j] += dp[j - num];
}
}
}
return dp[target];
}