问题描述
LeetCode 494. 目标和 (opens in a new tab)，难度中等。
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 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 +1 + 1 + 1 + 1 - 1 = 3
示例 2
输入：nums = [1], target = 1 输出：1
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
题解
解题思路：状态转移方程推导。对于数组中的每一个数字，我们都有两种选择，加上这个数字或者减去这个数字。假设我们已经处理到第 i 个数字，当前的目标值是 j。那么，有两种可能的情况：
- 我们可以加上
nums[i]，这样目标值变为j + nums[i]。在处理前i - 1个数字时，目标值为j + nums[i]的方法数量为dp[i - 1][j + nums[i]]。 - 我们可以减去
nums[i]，这样目标值变为j - nums[i]。在处理前i - 1个数字时，目标值为j - nums[i]的方法数量为dp[i - 1][j - nums[i]]。
因此，处理前 i 个数字，目标值为 j 的方法数量为 dp[i - 1][j + nums[i]] + dp[i - 1][j - nums[i]]。这就是状态转移方程。
在实际的代码中，我们需要注意数组的边界问题，只有当 j + nums[i] 和 j - nums[i] 在数组的范围内时，我们才能使用这个状态转移方程。所以，我们需要添加判断条件 if (j + nums[i - 1] < 2 * sum + 1) 和 if (j - nums[i - 1] >= 0)。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (Math.abs(target) > sum) return 0;
int[][] dp = new int[nums.length + 1][2 * sum + 1];
dp[0][sum] = 1;
for (int i = 1; i <= nums.length; ++i) {
for (int j = 0; j <= 2 * sum; ++j) {
if (j + nums[i-1] <= 2 * sum) {
dp[i][j] += dp[i-1][j + nums[i-1]];
}
if (j - nums[i-1] >= 0) {
dp[i][j] += dp[i-1][j - nums[i-1]];
}
}
}
return dp[nums.length][sum + target];
}
}class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
// 如果 target 的绝对值大于 sum，那么没有
if (Math.abs(target) > sum) return 0;
if ((target + sum) % 2 == 1) return 0;
int bagSize = (target + sum) / 2;
int[] dp = new int[bagSize + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; ++i) {
for (int j = bagSize; j >= nums[i]; --j) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
}