494. 目标和

一题目：

二 思路：

• 第一种思路：
  递归，每一位都可能为正或者为负，我们只要把买个位的情况考虑进去即可；
• 第二种思路：
  优化
  不难发现，在 DFS 的函数签名中只有「数值下标 index」和「当前结算结果 currSum」为可变参数，考虑将其作为记忆化容器的两个维度，返回值作为记忆化容器的记录值。
  由于 currSum 存在负权值，为了方便，我们这里不设计成静态数组，而是使用「哈希表」进行记录。

三 代码：

第一种思路：

class Solution {

    int count=0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums,target,0,0);
        return count;
    }

    private void dfs(int[] nums, int target, int index, int currSum) {
        if (index==nums.length){
            count+=currSum==target?1:0;
            return;
        }
        //前面一个数字是正的、负的
        dfs(nums,target,index+1,currSum+nums[index]);
        dfs(nums,target,index+1,currSum-nums[index]);
    }
}

优化：

class Solution {

    HashMap<String,Integer> cache=new HashMap<>();

    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums,target,0,0);
    }

    private int dfs(int[] nums, int target, int index, int currSum) {
        String key=index+"_"+currSum;

        if (cache.containsKey(key)){
            return cache.get(key);
        }
        //前面一个数字是正的、负的
        if (index==nums.length){
            //最后结果判断是否可以达成目标，然后进行回溯
            cache.put(key,currSum==target?1:0);
            return cache.get(key);
        }

        int incr=dfs(nums,target,index+1,currSum+nums[index]);
        int decr=dfs(nums,target,index+1,currSum-nums[index]);
        cache.put(key,incr+decr);
        return cache.get(key);
    }
}
``