target sum solution

Question

Hi bobo老师,
对于494. Target Sum 这道题目，我使用了记忆化搜索的形式解决了，并且accepted, 但是想不出怎么用dp来解决，能给一些思路么？

下面是我的记忆化搜索的方法：

class Solution {
    class Pair {
        int index;
        int target;
        public Pair(int index, int target) {
            this.index = index;
            this.target = target;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return index == pair.index && target == pair.target;
        }

        @Override
        public int hashCode() {
            return Objects.hash(index, target);
        }        
    }
    
    public int findTargetSumWays(int[] nums, int target) {
        if (nums.length == 0){
            return 0;
        }
        // use memory to save the method consider from index i to sum the target
        Map<Pair,Integer> memory = new HashMap<>();
        return ways(nums, 0 , target , memory);
    }
    
    public int ways(int[] nums, int index, int target, Map<Pair,Integer> memory){
        if (index == nums.length -1){
            int res = 0;
            if (target == nums[index]){
                res++;
            }
            if (target == -nums[index]){
                res++;
            }
            return res;
        }
        Pair pair = new Pair(index,target);
        if (memory.get(pair) != null){
            return memory.get(pair);
        }
        int result = 0;
        Pair pair1 = new Pair(index + 1, target - nums[index]);
        Pair pair2 = new Pair(index + 1, target + nums[index]);
        if (memory.get(pair1) != null){
            result = result + memory.get(pair1);
        } else {
            int a = ways(nums , index + 1 , target - nums[index] , memory);
            memory.put(pair1 , a);
            result = result + a;
        }
        if (memory.get(pair2) != null){
            result = result + memory.get(pair2);
        } else {
            int b = ways(nums , index + 1 , target + nums[index] , memory);
            memory.put(pair2, b);
            result = result + b;
        }
        return result;
    }
}

Answer 1

liuyubobobo 2022-09-24 15:54:25

整体思路是：

dp[i][s] 表示的是：使用 i 个数字，可以构成和为 s 的方案数。(注意，i 是使用的数字个数，而不是 nums 的索引)。

则最终结果为 dp[n][target]。

状态转移是：

dp[i][s] = dp[i - 1][s - nums[i - 1]] + dp[i - 1][s + nums[i - 1]]

即：使用  i 个数字，可以构成和为 s 的方案数，可以由两种方式组成：

第一种方式：使用 i - 1 个数字构成 s - nums[i - 1]，然后在第 i 个数字，为 nums[i - 1] 赋上正号（第 i 个数字的索引是 i - 1）

即：(s - nums[i - 1]) + nums[i - 1] = s

第一种方式：使用 i - 1 个数字构成 s + nums[i - 1]，然后在第 i 个数字，为 nums[i - 1] 赋上负号。

即 (s + nums[i - 1]) - nums[i - 1] = s

初始：dp[0][0] = 1，其余 dp[0][x] = 0。即使用 0 个数字，只有一种方案构成 0。

在下面的具体实现上，有一个小“技巧”。

在这个问题中，s 可能是负数，所以不能直接用 s 做索引。我们需要把 s “平移成”正数。

假设 nums 中所有数字加在一起是 sum，则 nums 中的数字可以组成的数字范围是 [-sum, sum] （一共 2 * sum + 1 种可能。）

我们给每一个 s 加上一个 sum，就能保证其在正数范围。

即：[-sum, sum] + sum = [0, 2 * sum]。这样一来，任何一个 s 对应的实际索引，是 s + sum。（在下面的代码中，我叫 offset，表示偏移量。）

更具体可以参考下面的代码和注释：

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
        
        int sum = 0;
        for(int num: nums) sum += num;
        
        // 如果 target 不在 [-sum, sum] 的范围，肯定得不到 target，直接返回 0
        if(target < -sum || target > sum) return 0;
        
        int n = nums.length;
        int[][] dp = new int[n + 1][2 * sum + 1];
        // 这里注意 dp 的空间大小，第一维度的范围是 [0, n]，所以大小是 n + 1
        // 第二维度承载 [-sum, sum] 之间的所有可能，所以大小是 [0, 2 * sum + 1]
        
        
        int offset = sum;
        dp[0][0 + offset] = 1;
        // 初始 0 个数字只能构成 0。注意在第二个维度，实际的和要加上偏移量
        // 所以是 dp[0][0 + offset] = 1
        
        // dp 过程
        for(int i = 1; i <= n; i ++){
            for(int s = -sum; s <= sum; s ++){
                
                // 求解 dp[i][s + offset]，依然是，要加 偏移量
                
                // s 可能来自 i - 1 个数字构成 s + nums[i - 1] 或者 s - nums[i - 1] 两种可能
                // 注意实际实现的时候，要判数组是否越界
                if(-sum <= s + nums[i - 1] && s + nums[i - 1] <= sum)
                    dp[i][s + offset] += dp[i - 1][s + nums[i - 1] + offset];
                if(-sum <= s - nums[i - 1] && s - nums[i - 1] <= sum)
                    dp[i][s + offset] += dp[i - 1][s - nums[i - 1] + offset];
            }
        }
        
        // 最终结果是 dp[n][target + offset]，依然是，不要忘了偏移量
        return dp[n][target + offset];
    }
}

==========

另外，非常重要的，这个问题的 n 最大为 20，所以枚举所有的加符号的可能，只有 2^20 = 100w 种可能。这个数据规模是不会超时。强烈建议试试看。

继续加油！：）