思路
有想到这里 0和1的数量是两个维度,但被之前的题目影响,想成单独处理维度了。
但其实这里是添加维度!
也就是说,原来01背包的二维解法变成三维,一维解法变成二维!
坑
不会统计数组字符串里的值,
用for…of(不是for…in!它遍历的是索引)
此时 dp[i][j]表示最多i个0和j个1时的最大子集长度,物品个数是strs数组长度
var findMaxForm = function(strs, m, n) {
let zeroNum //0
let oneNum //1
// dp[i][j]表示最多i个0和j个1时的最大子集长度
let dp =new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0))
for(let s of strs){
zeroNum =0
oneNum =0
// 写错成for...in,遍历的是索引(string)
for(let c of s){
if(c ==='0'){
zeroNum++
}else{
oneNum++
}
}
// 这里遵循的原则 其实是01背包的一维滚动数组版本!!只是写成了二维!
// 这道题在原来的01背包上,加了一个维度!
for(let i =m;i>=zeroNum;i--){
for(let j=n;j>=oneNum;j--){
dp[i][j] =Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
}
}
}
return dp[m][n]
};