LeetCode -- Dynamic Programming例

今天写的题和之前的题目还比较类似，比较不同的点是dp的长度稍有变化。

Target Sum

题目大意是通过给数组里的数加上+-号，使得他们组成target，要求返回一共有多少组这样的组合。

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

这一题中，我们继续延续coin change 2的思想。一层一程地计算。但是不一样的是，这些数字能够组成的和，不都在0-S这个范围内。这个范围应该是[-sum, sum]，sum是指数组里所有数的和。

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if (S > sum || S < -sum) {
            return 0;
        }
        int[][] dp = new int[nums.length+1][2*sum+1];
        dp[0][sum] = 1;
        for (int i = 1; i < nums.length+1; i++) {
            for (int j = 0; j < 2*sum+1; j++) {
                int v = 0;
                if (j - nums[i-1] >= 0) {
                    v += dp[i-1][j-nums[i-1]];
                }
                if (j + nums[i-1] < 2*sum+1) {
                    v += dp[i-1][j+nums[i-1]];
                }
                dp[i][j] = v;
            }
        }
        return dp[nums.length][S+sum];
    }
}