LeetCode 494. 目标和

每天一道DP防止抑郁

题目描述：

给定一个非负整数数组，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。

首先，我们来推导几个公式。
设nums数组中添加负号的数的和为SumN，nums数组中添加正号的数的和为SumP，数组的和为Sum。
由题意，我们可以得出：
SumP - SumN = S ==> SumP + SumP = S + SumN + SumP ==> 2 * SumP = S + Sum ==> SumP = (Sum + S) / 2。

所以这道题转化为从nums数组中选择数字求和，要求这个和等于Sum加上S除以二。求有总共有多少种情况。
这个问题进而转化为子集合问题，所以可以用0-1背包问题来解决这道题目。
状态转移方程为：dp[i] = dp[i] + dp[i - nums[i]] (dp[i] : 从nums中取数，使得这些数字的和为i的取法)

代码如下：

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        /*
            剪枝。如果全部选正号的和都小于S的话，怎么组合都达不到S
         */
        if (sum < S || (S + sum) % 2 == 1) {
            return 0;
        }
        int target = (S + sum) / 2;
        int[] dp = new int[target + 1];//dp[i]: 从nums中取数，使得这些数字的和为i的取法
        dp[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}