494. 目标总和
给你一个整数数组 nums 和一个整数目标。
您想要通过在 nums 中的每个整数之前添加符号“+”和“-”之一来构建 nums 的表达式，然后连接所有整数。
例如，如果 nums = [2, 1]，您可以在 2 之前添加一个“+”，在 1 之前添加一个“-”，并将它们连接起来构建表达式“+2-1”。
返回您可以构建的不同表达式的数量，其计算结果为目标。
示例1：
输入：nums = [1,1,1,1,1]，目标 = 3
输出：5
说明：有 5 种分配符号的方法，使 nums 的总和为目标 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]，目标 = 1
输出：1
限制：
1 0 0 -1000 原始页面
尽管回溯在这里很有用，我们可以使用动态规划来解决这个问题，以实现更低的时间复杂度。
public int findTargetSumWays(int[] nums, int target) {
/**
sum(neg) + sum(pos) = sum(nums);
sum(pos) - sum(neg) = target;
sum(pos) = (sum(nums) + target) / 2
*/
int sum = Arrays.stream(nums).sum();
// that means the sum of the positive number is invalid, because the nums do not conclude float
if((sum+target)%2 != 0|| Math.abs(target) > sum){
return 0;
}
// here we find the summary of the positive numbers
int pos = (sum + target) >>1;
// dp[i][j] array means for each index element `i` (nums[i]), if we want to reach the sum of the positive number `j`, we will have how many methods
int[][] dp = new int[nums.length+1][pos+1];
// if we want to reach 0 we will have 1 ways that means we choose nothing and there is nothing.
dp[0][0] = 1;
// if(nums[0] <= pos){
// dp[0][nums[0]] = 1;
// }
for(int i = 1; i <= nums.length; i++){
for(int j=0; j<=pos; j++){
if(nums[i-1] > j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
// Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
return dp[nums.length][pos];
}
