image.png

解法一

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         int absSum = 0; 
  4.         for(int num : nums){
  5.             absSum += Math.abs(num);
  6.         }
  7.         //如果nums中组合出来的最大值absSum < target
  8.         //那么直接返回0
  9.         if(Math.abs(target) > absSum){
  10.             return 0;
  11.         }
  12.         int n = nums.length;
  13.         //dp[i][j]表示考虑前i个数字，可以拼凑成数值j的组合方案
  14.         int[][] dp = new int[n + 1][2 * absSum + 1];
  17.         //如果对nums[]中的元素全部加上负号，则为-absSum，所以我们要做坐标偏移，
  18.         //且偏移量为absSum
  20.         //初始化,原本是初始化dp[0][0]=1，现在要加上坐标偏移量
  21.         dp[0][0 + absSum] = 1;
  23.         //状态转移方程
  24.         //dp[i][j] = dp[i - 1][j - nums[i]] + dp[i -1][j + nums[i]];
  25.         int bias = absSum;
  26.         for(int i = 1; i <= n; i++){
  27.             int val = nums[i - 1];
  28.             for(int j = -absSum; j <= absSum; j++){
  29.                 int case1 = j - val + bias >= 0 ? dp[i - 1][j - val + bias] : 0;
  30.                 int case2 = j + val + bias <= 2 * bias ? dp[i - 1][j + val + bias] : 0;
  31.                 dp[i][j + bias] += case1 + case2;
  32.             }
  33.         }
  35.         return dp[n][target + bias];
  36.     }
  37. }