题目描述
根据官方题解修改 好理解
代码
class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (S < -1000 || S > 1000) return 0;
int[][] dp = new int[nums.length + 1][2001];
if (nums[0] != 0) {
dp[1][nums[0] + 1000] = 1;
dp[1][-nums[0] + 1000] = 1;
} else {
// 正负2个方案 加上2
dp[1][nums[0] + 1000] += 2;
}
// 我们用 dp[i][j] 表示用数组中的前 i 个元素,组成和为 j 的方案数。
// 考虑第 i 个数 nums[i - 1],它可以被添加 + 或 -,因此状态转移方程如下:
// dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j + nums[i - 1]]
// 由于数组中所有数的和不超过 1000,那么 j 的最小值可以达到 -1000。
// 在很多语言中,是不允许数组的下标为负数的,
// 因此我们需要给 dp[i][j] 的第二维预先增加 1000,即:
// dp[i][j + 1000] = dp[i - 1][j - nums[i - 1] + 1000] + dp[i - 1][j + nums[i - 1] + 1000]
for (int i = 1; i <= nums.length; i++) {
for (int j = -1000; j <= 1000; j++) {
if (j - nums[i - 1] + 1000 >= 0) {
dp[i][j + 1000] += dp[i - 1][j - nums[i - 1] + 1000];
}
if (j + nums[i - 1] + 1000 <= 2000) {
dp[i][j + 1000] +=dp[i - 1][j + nums[i - 1] + 1000];
}
}
}
return dp[nums.length][S + 1000];
}
}