image.png

思路

有想到这里 0和1的数量是两个维度,但被之前的题目影响,想成单独处理维度了。
但其实这里是添加维度!
也就是说,原来01背包的二维解法变成三维,一维解法变成二维!

不会统计数组字符串里的值,
用for…of(不是for…in!它遍历的是索引

此时 dp[i][j]表示最多i个0和j个1时的最大子集长度,物品个数是strs数组长度

  1. var findMaxForm = function(strs, m, n) {
  2. let zeroNum //0
  3. let oneNum //1
  4. // dp[i][j]表示最多i个0和j个1时的最大子集长度
  5. let dp =new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0))
  6. for(let s of strs){
  7. zeroNum =0
  8. oneNum =0
  9. // 写错成for...in,遍历的是索引(string)
  10. for(let c of s){
  11. if(c ==='0'){
  12. zeroNum++
  13. }else{
  14. oneNum++
  15. }
  16. }
  17. // 这里遵循的原则 其实是01背包的一维滚动数组版本!!只是写成了二维!
  18. // 这道题在原来的01背包上,加了一个维度!
  19. for(let i =m;i>=zeroNum;i--){
  20. for(let j=n;j>=oneNum;j--){
  21. dp[i][j] =Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
  22. }
  23. }
  24. }
  25. return dp[m][n]
  26. };