DFS 深度优先遍历
解题思路
穷举出所有数字分别取正和负，再将穷举的 数字 与目标和 target 进行相加，则可以在 target = 0 时找到一个解；
若 nums 中有 n 个整数，每个数能取正负两种情况，则需要列举的情况有
2^n种；
实现代码
const findTargetSumWays = (nums, target) => {
/**
* @param {*} layer 当前递归树层数，也代表了当前操作考虑 nums 数组中第几个数字
* @param {*} nums
* @param {*} target 代表剩下的数字的目标和
* @returns
*/
const dfs = (layer, nums, target) => {
if (layer == nums.length) {
// nums 中所有数字考虑完毕，到达了递归树的叶结点，如果 target 为 0 代表当前结点是一个解
if (target == 0) res++;
return;
}
dfs(layer + 1, nums, target + nums[layer]); // nums[layer] 取负
dfs(layer + 1, nums, target - nums[layer]); // nums[layer] 取正
}
let res = 0;
dfs(0, nums, target);
return res;
};
子集法
问题转换
当目标和为 target 时：
- target = 正数组合 - 负数组合 ，正数组合 + 负数组合 = sum ，则 正数组合 - (sum - 正数组合) = target 推导出 正数组合 = (target + sum)/2；
- target 是固定的，sum 是固定的，正数组合 就可以求出来，此时问题就是在集合 nums 中找出和为 正数组合 的组合；
最后求出的 正数组合 一定是个偶数，则 sum + target 也一定是偶数；
解题思路
该方法需要从 nums 中找出一个子集，使其和的两倍为 sum + target；
与穷举法类似，但是对于每个数的策略变成了 （选 | 不选），递归树如下：
代码实现
const findTargetSumWays = (nums, target) => {
const dfs = (layer, nums, target) => {
// 表示已经考虑完所有数字
if (layer == nums.length) return target == 0 ? 1 : 0;
// 当前层开始考虑，目标和为 target 的数字组合的个数（当前解 = 不选当前数字的解 + 选当前数字的解）
return dfs(layer + 1, nums, target) + dfs(layer + 1, nums, target - nums[layer]);
}
// 1. 计算 target 与 nums 中数字的和
let sum = nums.reduce((a, b) => a + b) + target;
// 2. 判断 sum 是否是奇数或负数，是奇数或负数则无解
if (sum & 1 || sum < 0) return 0;
// 3. 是偶数并需要从 nums 中找出一个子集，使其和的两倍为 sum+target
return dfs(0, nums, sum / 2);
};
记忆化搜索
解题思路
在上面 子集法 的递归树中，许多子问题的答案被重复计算了；
可以使用记忆化搜索，定义一个 memo 数组保存每个子问题的计算结果，来避免这种重复计算；
代码实现
const findTargetSumWays = (nums, target) => {
const dfs = (layer, nums, target, memo) => {
// 找不到解了
if (target < 0) return 0;
// layer < 0 表示已经考虑完所有数字，直接判断 target 是否为 0 即可
if (layer == nums.length) return target == 0 ? 1 : 0;
// memo[layer][target] == -1 表示问题dfs(layer,nums,target,memo)这个子问题的解还没有被计算过
if (memo[layer][target] == -1) {
// 计算该问题的解并记录
memo[layer][target] = dfs(layer + 1, nums, target, memo) + dfs(layer + 1, nums, target - nums[layer], memo);
}
return memo[layer][target];
}
// 1. 计算 target 与 nums 中数字的和
let sum = nums.reduce((a, b) => a + b) + target;
// 2. 判断 sum 是否是奇数或负数，是奇数或负数则无解
if (sum & 1 || sum < 0) return 0;
// 3. 定义数组 memo 来记录 dfs 的计算结果，注意由于 dfs 中变化的参数有两个，所以 memo 是二维数组
// 数组列宽为 sum / 2 + 1，因为 memo[nums.length-1][sum / 2] 是问题的解
const memo = new Array(nums.length).fill('').map(it => new Array(sum / 2 + 1).fill(-1));
// 4. 是偶数并需要从 nums 中找出一个子集，使其和的两倍为 sum
return dfs(0, nums, sum / 2, memo);
};
动态规划
解题思路
实际上在 记忆化搜索 中使用了递归，如果直接从递归树的叶结点开始从上计算到根结点，是不是就可以省略递归中的 递 这个过程了呢，当然自底向上的计算需要做好准备工作，将上面的 memo 数组改名为 dp，但是两者表示的含义是一样的；
确定 dp 数组以及下标的含义：dp[i][j] 的含义为 从下标为 [0, i] 的物品里任意取，且重量总和不超过 j 时，背包能装下物品的 最大价值总和，nums 为物品数组、重量数组；
确定递推公式：根据每个数值只能搭配 + / − 使用，可得 dp[i][j] = dp[i − 1][j − nums[i − 1]] + dp[i − 1][j + nums[i − 1]]
如何初始化 dp 数组：
- dp[0][0] 表示为递归树中的叶节点，表示考虑完 nums 中所有数且 target 已经为 0 的情况(即找到了一个解)，所以 dp[0][0] 需要初始化为 1；
- 如果 nums[0] = 0，则选、不选它都能构成 target = 0 的解，所以解有两个 dp[0][0] = 2；
背包容量 j 0 1 2 3 4 dp[0][j] 1 1 0 0 0 dp[1][j] 0 0 0 0 0 dp[2][j] 0 0 0 0 0 dp[3][j] 0 0 0 0 0 dp[4][j] 0 0 0 0 0 确定遍历顺序：
- 先遍历物品、先遍历背包重量都可以，但是先遍历物品更好理解；
- 此题先遍历物品，再遍历背包；
举例推导 dp 数组：
背包容量 j 0 1 2 3 4 dp[0][j] 1 1 0 0 0 dp[1][j] 1 2 1 0 0 dp[2][j] 1 3 3 1 0 dp[3][j] 1 4 6 4 1 dp[4][j] 1 5 10 10 5
代码实现
const findTargetSumWays = (nums, target) => {
// 1. 计算 target 与 nums 中数字的和
const sum = nums.reduce((a, b) => a + b) + target;
// 2. 判断 sum 是否是奇数或负数，是奇数或负数则无解
if (sum & 1 || sum < 0) return 0;
// 3. 声明 dp 数组
const halfSum = sum >> 1;
const dp = new Array(nums.length).fill('').map(it => new Array(halfSum + 1).fill(0));
// 4. 初始化 dp，因为是自下而上计算，所以需要先给出最小规模问题的解
// 注意：dp[0][0] 表示为递归树中的叶节点，表示考虑完nums中所有数且target已经为0的情况(即找到了一个解)，所以dp[0][0]需要初始化为1
dp[0][0] = 1;
if (nums[0] == 0) {
// 如果 nums[0] = 0，则选、不选它都能构成 target = 0 的解，所以解有两个；
dp[0][0] = 2;
} else {
for (let j = 0; j <= halfSum; j++) {
if (j == nums[0]) dp[0][j] = 1;
}
}
// 5. 自底向上计算
for (let i = 1; i < nums.length; i++) { // 遍历物品
for (let j = 0; j <= halfSum; j++) { // 遍历背包容量
if (j < nums[i]) { // 当前背包容量 < 物品重量，不放物品 i
dp[i][j] = dp[i - 1][j];
} else { // 放物品 i
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
}
// 6. 答案就是数组最后一个元素啦
return dp[nums.length - 1][halfSum];
};
// 打印 dp 数组
┌─────────┬───┬───┬────┬────┬───┐
│ (index) │ 0 │ 1 │ 2 │ 3 │ 4 │
├─────────┼───┼───┼────┼────┼───┤
│ 0 │ 1 │ 1 │ 0 │ 0 │ 0 │
│ 1 │ 1 │ 2 │ 1 │ 0 │ 0 │
│ 2 │ 1 │ 3 │ 3 │ 1 │ 0 │
│ 3 │ 1 │ 4 │ 6 │ 4 │ 1 │
│ 4 │ 1 │ 5 │ 10 │ 10 │ 5 │
└─────────┴───┴───┴────┴────┴───┘
动态规划-滚动数组
解题思路
实际上在 记忆化搜索 中使用了递归，如果直接从递归树的叶结点开始从上计算到根结点，是不是就可以省略递归中的 递 这个过程了呢，当然自底向上的计算需要做好准备工作，将上面的 memo 数组改名为 dp，但是两者表示的含义是一样的；
确定 dp 数组以及下标的含义：dp[j] 表示：填满 j 这么大容积的包，有 dp[j] 种方法；
确定递推公式：dp[j] += dp[j - nums[i]] 等价 dp[j] = dp[j] + dp[j - nums[i]]
- 如果不选第 i 个数（nums[i]）的话，则方法数为 dp[j]；
- 如果选了第 i 个数（nums[i]）的话，则方法数为 dp[j - nums[i]]；
- 所以方法总数为：dp[j] = dp[j] + dp[j - nums[i]]；
如何初始化 dp 数组：dp[0] = 1 为初始条件：代表不考虑任何数，凑出计算结果为 0 的方案数为 1 种；
确定遍历顺序：
- 先遍历物品，再遍历背包；
- 状态值的更新只和它上边和左边的元素有关，把空间投影到一行后，状态转移（填表）的时候，从右边到左边更新状态值；
举例推导 dp 数组：nums = [1,1,1,1,1]，target = 3
数组索引 j 0 1 2 3 4 填满 j 这么大容积的包，有 dp[j] 种方法 1 5 10 10 5
代码实现
const findTargetSumWays = (nums, target) => {
// 1. 计算 target 与 nums 中数字的和
const sum = nums.reduce((a, b) => a + b) + target;
// 2. 判断 sum 是否是奇数或负数，是奇数或负数则无解
if (sum & 1 || sum < 0) return 0;
// 3. 定义 dp 数组，并初始化
const halfSum = sum >> 1;
let dp = new Array(halfSum + 1).fill(0);
dp[0] = 1;
// 4. 是偶数并需要从 nums 中找出一个子集，使其和的两倍为 sum+target
for (let i = 0; i < nums.length; i++) {
for (let j = halfSum; j >= nums[i]; j--) {
dp[j] = dp[j] + dp[j - nums[i]];
}
}
// 5. 答案就是数组最后一个元素
return dp[halfSum];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1049. 最后一块石头的重量 II
上一篇
评论
