leetcode494_目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-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

一共有5种方法让最终目标和为3。
注意:

数组的长度不会超过20，并且数组中的值全为正数。
初始的数组的和不会超过1000。
保证返回的最终结果为32位整数。

思路：

本题一看就是没有见过的动态规划  但是进行变化

//       可以化成两部分之差  target = sum(P) - sum(N)；
//        那么sum(P) + sum(N) + sum(P) - sum(N) = sum(S) + target ；
//      2sum(P)= sum(S) + target ；
//        那么sum(P) = [target + sum(S)] / 2；

一维动态

// 改一维 对dp[i][j]而言 相当于每个都依赖上一行的相同位置 和 上一行左边位置 所以得从后往前遍历更新 保证不会先覆盖上一行左边的值
	public static int findTargetSumWays2(int[] nums, int S) {
		int sum = 0;
		for (int i : nums) {
			sum += i;
		}
		if (sum < S || (sum + S) % 2 != 0) {
			return 0;
		}
		int target = (S + sum) / 2;
		// 寻找和为target的种数
		int[] dp = new int[target + 1];

		dp[0] = 1;
		// 在每一个位置都可以选择是否要当前位置的数
		for (int i = 0; i < nums.length; i++) { // 从1位置开始
			for (int j = target; j >= nums[i]; j--) {
				// 要当前值nums[i] 和 不要当前值nums[i]
				dp[j] = dp[j] + dp[j - nums[i]];

			}
		}
		return dp[target];
	}