494. Target Sum
一刷题，暴力解必须要想得到吧，一般能dp的都是从dfs到+memorization到dp. 对了如果实在不想用global变量的话可以写一个int[0] arr当参数穿，最后res = arr[0]返回就行。
DFS
class Solution {
public int res = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0){
return res;
}
helper(nums, S, 0, 0);
return res;
}
private void helper(int[] nums, int target, int pos, int sum){
if (pos == nums.length){
if (sum == target){
res++;
}
return;
}
helper(nums, target, pos + 1, sum + nums[pos]);
helper(nums, target, pos + 1, sum - nums[pos]);
}
}
然后是dp解法，为此专门做了一下416. Partition Equal Subset Sum弄懂如何在一个integer array里面找到subset which sum to a target. 这个题转换了一下原问题到新的角度，我们可以把原来的数组里的数分成两部分，一部分前面用加号，一部分前面用减号，他们的和是S, 这样可以得到正号部分的和是sum = (sum + S) / 2, 这样的话问题就转化为求原数组有多少种方法找到和为sum的subsets. 这里用到了416的0-1背包法， dp[i] 表示找到和为i的子数组的方法有多少种，则我们求的是dp[sum].
class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0){
return 0;
}
int sum = 0;
for (int num : nums){
sum += num;
}
if (sum < S || (sum + S) % 2 != 0){
return 0;
}
sum = (sum + S) / 2;
int[] dp = new int[sum + 1];
dp[0] = 1;
for (int num : nums){
for (int i = sum; i >= num; i--){
dp[i] += dp[i - num];
}
}
return dp[sum];
}
}
这里很关键的一点是转移方程里面，我们是从i = sum -> i = num的，为什么要这么做呢？一开始我也卡住了很久，始终没明白，后来还是看到了http://blog.csdn.net/mine_song/article/details/70216562的粗暴枚举才产生了感性认识，一下子顿悟了。
for (int num : nums){
for (int i = sum; i >= num; i--){
dp[i] += dp[i - num];
}
}
举例说明：给定集合nums={1,2,3,4,5}, 求解子集，使子集中元素之和等于9 = new_target = sum(P) = (target+sum(nums))/2.
比如当前元素为1的时候，我们是先计算dp[9], dp[8], dp[7]....dp[1], 为什么不按照i = num -> i = sum呢？ 如果我们那样做，dp[1] = dp[1] + dp[1 - 1]这里的意思就是要得到sum = 1, 我们可以选择不选择当前元素dp[1]和选择当前元素dp[1-1]的总和来得到sum = 1. 那么我们继续看dp[2], dp[2] = dp[2] + dp[2-1] = dp[2] + dp[1]这里的意思就是要得到sum = 2, 我们可以选择当前元素1， 也可以不选择当前元素1.但是有一个问题，就是我们这里的dp[2 - 1] = dp[1]虽然表示不选择当前元素1， 但是由于我们先更新的dp[1], 而且当时在更新dp[1]的时候就已经考虑了选择当前元素或者不选择当前元素两种情况才得到的总情况数目，而这里再次调用dp[1]来表示不选择当前元素来构成sum = 2的情况数，肯定是有重复计算的，结果会多出正确值。
如果我们从i = sum ->i = num, 比如dp[9] = dp[9] + dp[9 - 1] = dp[9] + dp[8],也就是得到sum = 9, 可以有两种情况，一种是不算当前元素的其他元素和就已经为9的情况dp[9], 和另一种算上当前元素才和为9，其他元素的和其实就为8的情况dp[8], 两者之和就是总情况数。 然后继续看dp[8] = dp[8] + dp[7], 也就是说要sum = 8, 分两种情况，一种是不算当前元素和就为8dp[8],以及算上当前元素才和为8其他元素的和为7的dp[7]种情况。 这样算下去就不会有重复计算。
那关于为什么下限等于num呢？因为sum < num的话，num的存在对于方案总数没有任何影响，不考虑。
定义dp[10]数组, dp[10] = {1,0,0,0,0,0,0,0,0,0}
dp[i]表示子集合元素之和等于当前目标值的方案个数, 当前目标值等于9减去当前元素值
当前元素等于1时，dp[9] = dp[9] + dp[9-1]
dp[8] = dp[8] + dp[8-1]
...
dp[1] = dp[1] + dp[1-1]
当前元素等于2时，dp[9] = dp[9] + dp[9-2]
dp[8] = dp[8] + dp[8-2]
...
dp[2] = dp[2] + dp[2-2]
当前元素等于3时，dp[9] = dp[9] + dp[9-3]
dp[8] = dp[8] + dp[8-3]
...
dp[3] = dp[3] + dp[3-3]
当前元素等于4时，
...
当前元素等于5时，
...
dp[5] = dp[5] + dp[5-5]
最后返回dp[9]即是所求的解
