题目及测试
package pid494;
/*494. 目标和给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例：输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3一共有5种方法让最终目标和为3。提示：数组非空，且长度不会超过 20 。初始的数组的和不会超过 1000 。保证返回的最终结果能被 32 位整数存下。*/public class main {public static void main(String[] args) {int[][] testTable = {
{1,2,3,2},{1,2,3,4},{1,1,1,3,3,4,3,2,4,2},{3,2,1,5,6,4}};for (int[] ito : testTable) {test(ito,2);}}private static void test(int[] ito,int k) {Solution solution = new Solution();int rtn;long begin = System.currentTimeMillis();for (int i = 0; i < ito.length; i++) {System.out.print(ito[i]+" "); }System.out.println();//开始时打印数组rtn = solution.findTargetSumWays(ito,k);//执行程序long end = System.currentTimeMillis(); //System.out.println(ito + ": rtn=" + rtn);System.out.println(": rtn=" +rtn);System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}
没想出来
解法1（别人的）
这道题也是一个常见的背包问题，我们可以用类似求解背包问题的方法来求出可能的方法数。
我们用 dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数。考虑第 i 个数 nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
也可以写成递推的形式：
dp[i][j + nums[i]] = dp[i][j + nums[i]] + dp[i - 1][j]
dp[i][j - nums[i]] = dp[i][j - nums[i]] + dp[i - 1][j]
其实就是，对于之前i-1的情况，和为j，现在有i的情况，会出现j+nums[i]和j-nums[i]的情况
由于数组中所有数的和不超过 1000，那么 j 的最小值可以达到 -1000。在很多语言中，是不允许数组的下标为负数的，因此我们需要给 dp[i][j] 的第二维预先增加 1000，即：
dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
public class Solution {public int findTargetSumWays(int[] nums, int S) {int[][] dp = new int[nums.length][2001];dp[0][nums[0] + 1000] = 1;dp[0][-nums[0] + 1000] += 1;for (int i = 1; i < nums.length; i++) {for (int sum = -1000; sum <= 1000; sum++) {if (dp[i - 1][sum + 1000] > 0) {dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];}}}return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];}
}解法2（别人的）
我们发现，方法二中动态规划的状态转移方程中，dp[i][...] 只和 dp[i - 1][...] 有关，因此我们可以优化动态规划的空间复杂度，只需要使用两个一维数组即可。
public class Solution {public int findTargetSumWays(int[] nums, int S) {int[] dp = new int[2001];dp[nums[0] + 1000] = 1;dp[-nums[0] + 1000] += 1;for (int i = 1; i < nums.length; i++) {int[] next = new int[2001];for (int sum = -1000; sum <= 1000; sum++) {if (dp[sum + 1000] > 0) {next[sum + nums[i] + 1000] += dp[sum + 1000];next[sum - nums[i] + 1000] += dp[sum + 1000];}}dp = next;}return S > 1000 ? 0 : dp[S + 1000];}
}