題目

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

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

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

答案

巨短的dfs答案

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        return dfs(nums, 0, 0, S);
    }
    
    public int dfs(int[] nums, int index, int curr_sum, int S) {
        if(index == nums.length) return (curr_sum == S)?1:0;
        int ways = dfs(nums, index + 1, curr_sum + nums[index], S) + dfs(nums, index + 1, curr_sum - nums[index], S);
        return ways;
    }
}

下面用dp 優(yōu)化下時間
這道題要改成dp有點tricky
我本來的想法是在dfs遞歸計算的同時記錄 dp[當(dāng)前的sum][當(dāng)前的index]的值
但是這樣做有個問題刻像，就是curr_sum是有可能小于0的萍肆，這樣就會引發(fā)異常

所以我想偷懶用HashMap來替代dp數(shù)組，代碼如下

class Solution {
    class Pair {
        int curr_sum;
        int index;
        public Pair(int sum, int i) { curr_sum = sum; index = i;}
    }

    public int findTargetSumWays(int[] nums, int S) {
        Map<Pair, Integer> dfs_memory = new HashMap<Pair, Integer>();
        return dfs(nums, dfs_memory, 0, 0, S);
    }

    public int dfs(int[] nums, Map<Pair, Integer> dfs_memory, int index, int curr_sum, int S) {
        if(index == nums.length) {
            return (curr_sum == S)?1:0;
        }
        Pair key = new Pair(curr_sum, index);
        Integer memorized = dfs_memory.get(key);
        if(memorized == null) {
            int ways = dfs(nums, dfs_memory, index + 1, curr_sum + nums[index], S);
            ways += dfs(nums, dfs_memory, index + 1, curr_sum - nums[index], S);
            dfs_memory.put(key, ways);
            return ways;
        }
        return memorized;
    }
}

大概Hashmap有點慢，竟然超時了

最后調(diào)整了一下dp數(shù)組的細(xì)節(jié)就過了嗓违，代碼如下

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[][] dfs_memory = new int[2001][nums.length];
        for(int i = 0; i < dfs_memory.length; i++) Arrays.fill(dfs_memory[i], -1);
        return dfs(nums, dfs_memory, 0, 0, S);
    }

    public int dfs(int[] nums, int[][] dfs_memory, int index, int curr_sum, int S) {
        if(index == nums.length) {
            return (curr_sum == S)?1:0;
        }
        int adjusted_currsum = curr_sum + 1000;
        if(dfs_memory[adjusted_currsum][index] == -1) {
            dfs_memory[adjusted_currsum][index] = dfs(nums, dfs_memory, index + 1, curr_sum + nums[index], S);
            dfs_memory[adjusted_currsum][index] += dfs(nums, dfs_memory, index + 1, curr_sum - nums[index], S);
        }
        return dfs_memory[adjusted_currsum][index];
    }
}