algo/di-er-zhan-a01c6/bei-bao-le-34bd4/mu-biao-he-94198/

[giscus[bot]]

algo/di-er-zhan-a01c6/bei-bao-le-34bd4/mu-biao-he-94198/

Info 数据结构精品课 (https://labuladong.online/algo/ds-class/) 和 递归算法专题课 (https://labuladong.online/algo/tree-class/) 限时附赠网站会员；算法可视化编辑器上线，点击体验 (https://labuladong.online/algo-visualize...

https://labuladong.github.io/algo/di-er-zhan-a01c6/bei-bao-le-34bd4/mu-biao-he-94198/

[Yegezw]

贴一个记忆化搜索的思路（因为target可能为负数，因此memo不能为二维数组）

public class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        memo = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            memo.add(new HashMap<>());
        }
        return dp(nums, nums.length - 1, target);
    }

    private List<Map<Integer, Integer>> memo; // memo[index][target]

    // 返回用 nums[0 ... index] 构造出 target 的次数
    private int dp(int[] nums, int index, int target) {
        if (index == -1 && target == 0) return 1;
        if (index == -1) return 0;

        if (!memo.get(index).containsKey(target)) {
            int res = 0;
            int num = nums[index];
            res += dp(nums, index - 1, target - num);
            res += dp(nums, index - 1, target + num);

            memo.get(index).put(target, res);
        }

        return memo.get(index).get(target);
    }
}