动态规划和回溯算法到底谁是谁爹？ :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：动态规划和回溯算法到底谁是谁爹？

评论礼仪 见这里，违者直接拉黑。

[wozien]

if(sum + target < 0 || (sum + target) % 2) return 0 判断条件需要这样

[innovationb1ue]

使用Python解题， 文中代码逻辑 sum < target 应该改为 sum < abs(target) 不然报错

例：
输入：
[100]
-200

此时target < sum 不触发提前返回特殊值。但在DP数组定义时 由于(sum + target) / 2 是负数，所以DP数组其实为空。后续for循环触发异常。

[Brandy0k]

sum(A) - sum(B) = target 这个式子怎么理解。为什么不是sum(A)+ sum(B) = target

[FrankYJY]

都是只能加减，所以最后是一个全都是加的子集A加上一个全都是减的B，全都是减的B=-全都是加的B，a1+a2...-b1-b2...=target，sum(A) - sum(B) = target。因为全都用上所以B=A的补集，sum(A) + sum(B) = sum(nums)，当然这里的集不是集合

[SunnyXiaoWei]

(sum(nums) + target) % 2 为负数时，会导致角标越界，抛出异常
题目给出，nums数组的元素是非负整数，也就是说 nums 是不可能凑出负数子集，所以只需要return 0即可

[hujunwei]

dp解法答案好像不对

[labuladong]

感谢各位指出的问题，力扣的题目改了，我之前没有考虑到 target 为负数的情况，文中解法已修复

[lumaster]

Base case那段解释有点疑惑：

dp[..][0] = 1，因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。

假设 nums[]=[0, 0, 0] , sum=0, 那么有 dp[0][0]=1, dp[1][0]=2 , dp[2][0]=4，跟题解的 dp[..][0]=1有悖。

官方的Base case是：

因此在dp转移里需要从 j = 0 开始遍历，因为在nums[i] = 0的情况下，dp[..][0]=1的说法并不正确

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
            if (j >= nums[i-1]) {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            } else {
                // 背包的空间不足，只能选择不装物品 i
                dp[i][j] = dp[i-1][j];
            }
        }
    }

[labuladong]

@lumaster 你说的有道理，是我考虑的有纰漏，base case 应该仅仅是 dp[0][0] = 1，而不应该是 dp[..][0] = 1，文中已改正！

[renlindong]

不太认同文中说的为了美观，而选择不加参数的做法，那样写反而增加了理解成本不是吗？

function findTargetSumWays(nums: number[], target: number): number {
  let result = 0
  const helper = (nums: number[], i: number, sum: number) => {
    if(i === nums.length) {
      if(sum === target) {
        result++
      }
      return
    }
    sum += nums[i]
    helper(nums, i + 1, sum)
    sum -= nums[i]

    sum -= nums[i]
    helper(nums, i + 1, sum)
    sum += nums[i]
  }
  helper(nums, 0, 0)
  return result
};

[morganwu277]

真没必要纠结这个，这个不是本质。

[hwhaocool]

@Brandy0k

sum(A) - sum(B) = target 这个式子怎么理解。为什么不是sum(A)+ sum(B) = target

一个添加+，一个添加-， 其实就是你理解的 sum(A) + (-sum(B)) = target = sum(A) - sum(B)

[lzh2580]

@renlindong 思路不同，正常人喜欢累加，目标值知道就可以减呀

[E4verett]

(sum + target)%2 == 1：sum和target一定要么都是奇数要么都是偶数，因为我们的目标是将sum进行符号变换进而得到target，而对sum中每个数的符号进行改变，变化量一定是偶数

[AlexHongYX]

我理解累加和累减的区别：
累加：target + nums[i]，如果nums[i]选择+号，则target+(+nums[i])->target+nums[i]；如果nums[i]选择-号，则target+(-nums[i])->target-nums[i]
累减：target-nums[i]，如果nums[i]选择+号，则target-(+nums[i])->target-nums[i]；如果nums[i]选择-号，则target-(-nums[i])->target+nums[i]

[bert82503]

打卡，感谢！

[UESTCrookieLI]

东哥，这篇文章的动态规划用的解法里，base case和之前一篇文章的感觉有点出入，让我迷茫了。这篇的base case是dp[0][..] = 0， dp[..][0] = 0, 唯独dp[0][0]=1，但是之前的完全背包问题是dp[0][..] = 0， dp[..][0] = 1。现在有点迷糊

[lhcezx]

贴一个直接DP法，由于j可能为负所以没法用数组保存，因此存在重复子问题计算，但C++依然能通过

class Solution {
public:
    //  返回从1到i个数中，目标和为j的组合数目
    int dp(vector<int>& nums, int i, int j) {
        if (i == -1) {
            if (j == 0) return 1;
            return 0;
        }
        //  对应两种选择，nums[i]为正号或nums[i]为负号
        return dp(nums, i - 1, j - nums[i]) + dp(nums, i - 1, j + nums[i]);
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        return dp(nums, n - 1, target);
    }
};

[labuladong]

@lhcezx 👍，其实这种情况也是可以用备忘录的，python 可以把元组 (i, j) 存到备忘录 dict 中 ，cpp 的话可以把字符串 string key = i + "," + j 作为 unordered_map 备忘录中的键。

[lhcezx]

@lhcezx 👍，其实这种情况也是可以用备忘录的，python 可以把元组 (i, j) 存到备忘录 dict 中 ，cpp 的话可以把字符串 string key = i + "," + j 作为 unordered_map 备忘录中的键。

@labuladong 感谢东哥回复，补充一下带备忘录版

class Solution {
    unordered_map<string, int> memo;
public:
    //  返回从1到i个数中，目标和为j的组合数目
    int dp(vector<int>& nums, int i, int j) {
        string key = to_string(i) + "," + to_string(j);
        if (memo.count(key)) return memo[key];
        if (i == -1) {
            if (j == 0) return 1;
            return 0;
        }
        //  对应两种选择，nums[i]为正号或nums[i]为负号
        return memo[key] = dp(nums, i - 1, j - nums[i]) + dp(nums, i - 1, j + nums[i]);
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        return dp(nums, n - 1, target);
    }
};

有一个小问题，我这里如果在key中的i和j之间不加逗号会得不到正确的答案，没想明白为什么一定要加一个逗号？能举个例子吗？

[labuladong]

@lhcezx 中间加一些特殊分隔符是为了表明这是一个数对儿，即 12,3 和 1,23 是不同的两对儿，如果不加特殊分隔符，12,3 和 1,23 都变成 123 了，会被判定成相同的数对儿，产生错误。

[guqihao-7]

补一个记忆化搜索，不拼接字符串，仍然使用二维int数组，速度比拼接字符串查HashMap要快点。index的取值范围是[0, nums.length]，sumOfPath的取值范围是[minVal, maxVal]，所以memo = new int[nums.length + 1][maxVal - minVal + 1]
sumOfPath可以是负数，但是数组下标不可以是负数，所以在向备忘录memo填值时需要有一个maxVal的偏移量

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            maxVal += nums[i];
        }
        minVal = -maxVal;
        memo = new int[nums.length + 1][maxVal - minVal + 1];
        for (int[] ints : memo) {
            Arrays.fill(ints, Integer.MIN_VALUE);
        }
        int ans = process(nums, 0, 0, target);
        return ans;
    }

    int[][] memo;

    int minVal = 0;
    int maxVal = 0;

    public int process(int[] nums, int index, int sumOfPath, int target) {
        if (index == nums.length) {
            return sumOfPath == target ? 1 : 0;
        }

        if (memo[index][sumOfPath + maxVal] != Integer.MIN_VALUE) {
            return memo[index][sumOfPath + maxVal];
        }

        memo[index][sumOfPath + maxVal] = process(nums, index + 1, sumOfPath + nums[index], target)
                + process(nums, index + 1, sumOfPath - nums[index], target);
        return memo[index][sumOfPath + maxVal];
    }
}

[Goolloo]

提供一下直接计算组合数量的思路

Solution.1 从上一行的可能的来源，计算当前数值的组合树

numConbinations[i][j] = numConbinations[i-1][j-num] + numConbinations[i-1][j+num]

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
        int numSize = nums.length;
        int sum = Arrays.stream(nums).sum();
        
        if(target > sum || target < -sum) {
            return 0;
        }
        
        // 1-number of numbers used
        // 2-add or minus
        // 3-result value
        int[][] numCombinations = new int[numSize + 1][sum + 1];
        
        // init
        // only result = 0 and 0 number to use, has 1 combination
        numCombinations[0][0] = 1;
        
        for(int i = 1; i <= numSize; i++) {
            int num = nums[i-1];
            for(int j = 0; j <= sum; j++) {
                // plus
                numCombinations[i][j] = numCombinations[i-1][Math.abs(j - num)];
                // minus
                if(j + num <= sum) {
                    numCombinations[i][j] += numCombinations[i-1][j + num];
                }
            }
        }
        
        // Arrays.stream(numCombinations).map(Arrays::toString).forEach(System.out::println);
        
        return numCombinations[numSize][Math.abs(target)];
    }
}

Solution.2 从上一行的组合数量，分发给下一行的组合数

for numConbinations[i][j]
=> numConbinations[i+1][j + num]
=> numConbinations[i+1][j - num]

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
        int numSize = nums.length;
        int sum = Arrays.stream(nums).sum();
        
        if(target > sum || target < -sum) {
            return 0;
        }
        
        // 1-number of numbers used
        // 2-plus or minus
        // 3-result value
        int[][] numCombinations = new int[numSize + 1][sum*2 + 1];
        
        // init
        // only result = 0 and 0 number to use, has 1 combination
        numCombinations[0][sum] = 1;
        
        for(int i = 1; i <= numSize; i++) {
            int num = nums[i-1];
            for(int j = 0; j < sum*2 + 1; j++) {
                // add count from last row, only when last row can reach
                if(numCombinations[i-1][j] == 0) {
                    continue;
                }
                
                // plus
                numCombinations[i][j + num] += numCombinations[i-1][j];
                // minus
                numCombinations[i][j - num] += numCombinations[i-1][j];
            }
        }
        
        // Arrays.stream(numCombinations).map(Arrays::toString).forEach(System.out::println);
        
        return numCombinations[numSize][sum + target];
    }
}

Comparison

Items	Solution.1-calculate from i-1	Solution.2-propagate to i+1
Calculating Negative Values	No need, values are started from 0, they are mirrored from 0	Need, j = 0 and j +- num = 0 need different treatments
Time Complexity	O(sum * num.size), need to check each cell	O(2^(n+1)-2), 2^0 + 2^1+2^2+...+2^n, exponentially expanding, at worst case
Space Complexity	(1+sum) * num.size	(1+2*sum)*num.size

[labuladong]

👍👍👍

[yonggui-yan]

打卡

[NOS-AE]

麻了，没想到可以这样转化

[zhlfml]

对照二维 dp，只要把 dp 数组的第一个维度全都去掉就行了，唯一的区别就是这里的 j 要从后往前遍历，原因如下：

因为二维压缩到一维的根本原理是，dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候，相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。

那么，我们就要做到：在计算新的 dp[j] 的时候，dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果。

如果你从前往后遍历一维 dp 数组，dp[j] 显然是没问题的，但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。

解释的妙，读了之后顿时有醐醍灌顶，茅塞顿开之感！！！

[holmeszheng2008]

HashMap<String, Integer> memo = new HashMap<>();
String key = i + "," + remain;
用java，构造string做memo的key，leetcode submit时用时高了好多，好像leetcode特别不喜欢java的字符串拼接

[holmeszheng2008]

本题和416. Partition Equal Subset Sum的区别是本题的num[i]可以=0，所以base case不能仅在remain==0的时候，必须是remain == 0 && index == -1

[holmeszheng2008]

例如在 bottom up解法中，base case是dp[0][0] = 1而不是dp[i][0] = 1

[chygithub2020]

回溯加备忘录后，子问题数也是n*m，n为数组大小，m为目标值，那dp的子问题数也是这么多，为什么dp会快这么多，是因为递归调用的开销吗？

[EyeDroplyq]

晕了

[yihang-gao]

有没有人发现最后的动态规划的思路，对于[0,0,0,0,0,0,1]这种存在0的是不适用的哇。应该先把0相关的踢掉

[Ruobing1997]

这里不明白二维的为什么j不能从1开始，我看子集背包问题里，二维的j是从1开始的，区别是那边先初始化了一下
其实主要是dp的定义问题，dp[i][0] 为什么是1，是什么都不装作为一种解法的意思吗