class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (nums.length == 0) {
return 0;
}
int sum = 0;
for (int num: nums) {
sum += num;
}
if (S > sum || S < -sum) {
return 0;
}
int[] dp = new int[2 * sum + 1];
dp[sum] = 1;
for (int i = 0; i < nums.length; i++) {
int[] next = new int[2 * sum + 1];
for (int j = 0; j < 2 * sum + 1; j++) {
if (j - nums[i] >= 0 && j + nums[i] < 2 * sum + 1) {
next[j - nums[i]] += dp[j];
next[j + nums[i]] += dp[j];
}
}
dp = next;
}
return dp[sum + S];
}
}
来源: http://www.bubuko.com/infodetail-2285321.html