题解 | #目标和# [P3]

时间: O(maxSum*N)
空间: O(maxSum)

DP 定义:
  DP(i, j): # of ways num[0, i] can sum to j.
  DP(i, j) = DP(i-1, j + num[i]) + DP(i-1, j - num[i])

import java.util.*;

public class Solution {
    public int findTargetSumWays (int[] nums, int target) {
      if (nums.length == 0) return 0;

      // 0<=sum(nums[i])<=1000, so -1000 <= sum <= 1000
      int[] arrS = new int[2001];  
      // for arrS[j], j = sum + 1000;
      // for nums[0], sum = nums[0] or -nums[0]
      arrS[nums[0]+1000]++; arrS[-nums[0]+1000]++;
      
      for (int i = 1; i < nums.length; i++) {
        int tmp[] = new int[2001];
        int num = nums[i];
        // i-1的sum的范围是 [-1000+num, 1000-num]
        for (int sum = -1000+num; sum <= 1000-num; sum++) {
          int j = sum + 1000;       // j = sum + 1000;
          tmp[j+num] += arrS[j]; // +
          tmp[j-num] += arrS[j]; // -
        }
        // 为方便理解，若完全对照定义，上面的loop也可以写成：
        // int num = nums[i];
        // for (int sum = -1000; sum <= 1000; sum++) {
        //   int j = sum + 1000;
        //   if (j-num >= 0)
        //     tmp[j] += arrs[j-num];
        //   if (j+num <= 2000)
        //     tmp[j] += arrs[j+num];
        // }
        arrS = tmp;  // swap
      }
      
      return arrS[target + 1000];
    }
}