动态规划
解题思路
难点：
- 把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品，这道题就可以使用 0-1 背包 问题的思路完成，这里的目标值是能放进背包的字符串的数量；
- 物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选；
确定 dp 数组以及下标的含义：dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量；
确定递推公式：dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1)
如何初始化 dp 数组：将三维数组初始化成 0 即可；
确定遍历顺序：
- 遍历物品、先遍历背包重量都可以，但是先遍历物品更好理解；
- 此题先遍历物品，再遍历背包；
举例推导 dp 数组：这里只推导二维的 dp 数组，以 [“10”, “0001”, “111001”, “1”, “0”]，m = 3，n = 3 为例
k = 0 个 1 k = 1 个 1 k = 2 个 1 k = 3 个 1 j = 0 个 0 0 1 1 1 j = 1 个 0 1 2 2 2 j = 2 个 0 1 2 3 3 j = 3 个 0 1 2 3 3 j = 4 个 0 1 2 3 3 j = 5 个 0 1 2 3 4
代码实现
JavaScript
JavaScript
var findMaxForm = function (strs, m, n) {
const len = strs.length;
const dp = new Array(len + 1).fill(0).map(it => new Array(m + 1).fill(0).map(it => new Array(n + 1).fill(0)));
for (let i = 1; i <= len; i++) {
// 注意：有一位偏移
let count = countZeroAndOne(strs[i - 1]);
let zeros = count[0];
let ones = count[1];
for (let j = 0; j <= m; j++) {
for (let k = 0; k <= n; k++) {
let a = dp[i][j][k] = dp[i - 1][j][k];
let b = (j >= zeros && k >= ones) ? dp[i - 1][j - zeros][k - ones] + 1 : 0;
dp[i][j][k] = Math.max(a, b);
}
}
}
return dp[len][m][n];
};
const countZeroAndOne = (str) => {
const cnt = [0, 0];
[...str].forEach(num => {
cnt[num]++;
});
return cnt;
}
// 空间压缩
var findMaxForm = function (strs, m, n) {
const dp = new Array(m + 1).fill(0).map(it => new Array(n + 1).fill(0));
dp[0][0] = 0;
for (let i = 0; i < strs.length; i++) {
let count = countZeroAndOne(strs[i]);
let zeros = count[0];
let ones = count[1];
for (let j = m; j >= zeros; j--) {
for (let k = n; k >= ones; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
}
}
}
return dp[m][n];
};
const countZeroAndOne = (str) => {
const cnt = [0, 0];
[...str].forEach(num => {
cnt[num]++;
});
return cnt;
}
// dp 推导
┌─────────┬───┬───┬───┬───┐
│ (index) │ 0 │ 1 │ 2 │ 3 │
├─────────┼───┼───┼───┼───┤
│ 0 │ 0 │ 1 │ 1 │ 1 │
│ 1 │ 1 │ 2 │ 2 │ 2 │
│ 2 │ 1 │ 2 │ 3 │ 3 │
│ 3 │ 1 │ 2 │ 3 │ 3 │
│ 4 │ 1 │ 2 │ 3 │ 3 │
│ 5 │ 1 │ 2 │ 3 │ 4 │
└─────────┴───┴───┴───┴───┘
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 494. 目标和
上一篇
评论
