动态规划-滚动数组
解题思路
确定 dp 数组以及下标的含义：
- 01背包 中 dp[j] 表示：容量为 j 的背包，所背的物品价值最大可以为 dp[j]；
- 套到本题则 dp[j] 表示 背包总容量是 j ，放进物品后，背的最大重量为 dp[j]；
- 如果背包容量为 bagSize ，dp[bagSize] 就是装满背包之后的重量，所以当 dp[bagSize] == bagSize 的时候，背包就装满了；
确定递推公式：
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
- 01背包 的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；
- 本题相当于背包里放入数值，那么物品 i 的重量、价值也是 nums[i] ，递推公式与 01背包 的递推公式一样；
如何初始化 dp 数组：全部初始化成 0；
- 如果题目给的价值都是正整数，那么非 0 下标都初始化为 0 就可以了；
- 如果题目给的价值有负数，那么非 0 下标就要初始化为负无穷，这样才能让 dp 数组在递推的过程中取得最大的价值，而不是被初始值覆盖了；
确定遍历顺序：
- 先遍历物品，再遍历背包；
- 状态值的更新只和它上边和左边的元素有关，把空间投影到一行后，状态转移（填表）的时候，从右边到左边更新状态值；
举例推导 dp 数组：
- 解题关键：是否可以从输入数组中挑选出一些正整数，使得这些数的和 等于 整个数组元素的和的一半 => 数组的和一定是偶数；
- 如果 nums 的总和是偶数，那就可以将题意转化为，给定一个容量 sum/2 的背包，求其最多能装多重的石头，可以将 nums[i] 视为第 i 个石头的重量，如果 dp[j] == j 说明，集合中的子集总和正好可以凑成总和 j ，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等；
- 以 [1, 5, 11, 5] 为例：到达标记为
11的部分可以提前退出循环，不必执行后面的循环了 （这里展示出来是为了便于分析和理解）；
sum/2 的索引 j 0 1 2 3 4 5 6 7 8 9 10 11 nums[j] = 1 0 1 1 1 1 1 1 1 1 1 1 1 nums[j] = 5 0 1 1 1 1 5 6 6 6 6 6 6 nums[j] = 11 0 1 1 1 1 5 6 6 6 6 6 11nums[j] = 5 0 1 1 1 1 5 6 6 6 6 10 11
复杂度
-
时间复杂度：
O(NC)，这里 N 是数组元素的个数，C 是数组元素的和的一半； -
空间复杂度：
O(C)，减少了物品那个维度，无论来多少个数，用一行表示状态就够了；
代码实现
JavaScript
JavaScript
// 二维 dp
var canPartition = function (nums) {
// 1. 对 nums 求和 sum
const sum = nums.reduce((p, v) => p + v);
// 2. sum 如果为奇数一定不会出现「将这个数组分割成两个子集，使得两个子集的元素和相等」
if (sum & 1) return false;
// 3. 初始化 dp 滚动数组
const bagSize = sum / 2;
const weight = nums;
const value = nums;
const dp = new Array(nums.length).fill().map(_ => new Array(bagSize + 1).fill(0));
for (let i = weight[0]; i <= bagSize; i++) {
dp[0][i] = value[0];
}
// 4. 先遍历物品，再遍历背包容量
for (let i = 1; i < nums.length; i++) { // 遍历物品
for (let j = 0; j <= bagSize; j++) { // 遍历背包容量
// 更新 dp 数组
if (j < weight[i]) {
// 不放物品 i
dp[i][j] = dp[i - 1][j];
} else {
// 放物品 i
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
// 4-2. 找到了「将这个数组分割成两个子集，使得两个子集的元素和相等」提前结束循环
if (dp[i][j] === bagSize) return true;
}
}
// console.table(dp); // 打印 dp 数组
return dp[nums.length - 1][bagSize] === bagSize;
};
// 空间压缩 - 滚动数组
var canPartition = function (nums) {
// 1. 对 nums 求和 sum
const sum = nums.reduce((p, v) => p + v);
const bagSize = sum / 2;
// 2. sum 如果为奇数一定不会出现「将这个数组分割成两个子集，使得两个子集的元素和相等」
if (sum & 1) return false;
// 3. 初始化 dp 滚动数组
const dp = Array(sum / 2 + 1).fill(0);
// 4. 更新 dp 数组
for (let i = 0; i < nums.length; i++) {
for (let j = bagSize; j >= nums[i]; j--) {
// 4-1. 背包空间 j 一定要大于等于 物品大小 nums[i] 才能放入
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
// 4-2. 找到了「将这个数组分割成两个子集，使得两个子集的元素和相等」提前结束循环
if (dp[j] === bagSize) return true;
}
}
return dp[bagSize] === bagSize;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 96. 不同的二叉搜索树
上一篇
评论
