fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
动态规划和回溯算法到底谁是谁爹？ :: labuladong的算法小抄
使用Python解题， 文中代码逻辑 sum < target 应该改为 sum < abs(target) 不然报错
例： 输入： [100] -200
此时target < sum 不触发提前返回特殊值。但在DP数组定义时 由于(sum + target) / 2 是负数，所以DP数组其实为空。后续for循环触发异常。
(sum(nums) + target) % 2 为负数时，会导致角标越界，抛出异常 题目给出，nums数组的元素是非负整数，也就是说 nums 是不可能凑出负数子集，所以只需要return 0即可
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];
}
}
}
@lumaster 你说的有道理，是我考虑的有纰漏，base case 应该仅仅是 dp[0][0] = 1，而不应该是 dp[..][0] = 1，文中已改正！
不太认同文中说的为了美观，而选择不加参数的做法，那样写反而增加了理解成本不是吗？
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
};
@Brandy0k
sum(A) - sum(B) = target 这个式子怎么理解。为什么不是sum(A)+ sum(B) = target
一个添加+，一个添加-， 其实就是你理解的 sum(A) + (-sum(B)) = target = sum(A) - sum(B)
(sum + target)%2 == 1：sum和target一定要么都是奇数要么都是偶数，因为我们的目标是将sum进行符号变换进而得到target，而对sum中每个数的符号进行改变，变化量一定是偶数
我理解累加和累减的区别： 累加：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]
东哥，这篇文章的动态规划用的解法里，base case和之前一篇文章的感觉有点出入，让我迷茫了。这篇的base case是dp[0][..] = 0， dp[..][0] = 0, 唯独dp[0][0]=1，但是之前的完全背包问题是dp[0][..] = 0， dp[..][0] = 1。现在有点迷糊
东哥，这篇文章的动态规划用的解法里，base case和之前一篇文章的感觉有点出入，让我迷茫了。这篇的base case是dp[0][..] = 0， dp[..][0] = 0, 唯独dp[0][0]=1，但是之前的完全背包问题是dp[0][..] = 0， dp[..][0] = 1。现在有点迷糊
前面的完全背包问题是硬币币种的选择，硬币的面额不可能存在0; 分割子集那道题对应的也是集合中全部都是正整数，因此可以用dp[...][0]概括所有base case，这里数组中出现的元素可能等于0，因此没法统一概括了只有dp[0][0]可以为1
贴一个直接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);
}
};
@lhcezx 👍，其实这种情况也是可以用备忘录的，python 可以把元组 (i, j) 存到备忘录 dict 中 ，cpp 的话可以把字符串 string key = i + "," + j 作为 unordered_map 备忘录中的键。
@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之间不加逗号会得不到正确的答案，没想明白为什么一定要加一个逗号？能举个例子吗？
@lhcezx 中间加一些特殊分隔符是为了表明这是一个数对儿，即 12,3 和 1,23 是不同的两对儿，如果不加特殊分隔符，12,3 和 1,23 都变成 123 了，会被判定成相同的数对儿，产生错误。
补一个记忆化搜索，不拼接字符串，仍然使用二维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];
}
}
提供一下直接计算组合数量的思路
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 |
