题意理解:
给你一个二进制字符串数组
strs
和两个整数m
和n
。请你找出并返回
strs
的最大子集的长度,该子集中 最多 有m
个0
和n
个1
。如果
x
的所有元素也是y
的元素,集合x
是集合y
的 子集 。
将字符串0和1的个数看作是该字符串的两个维度,假设将其看作物品的重量和体积。
那么m和n就是对背包的限制:承重量为m, 体积为的背包。
求元素最多的子集,该问题可以转换为:求装满承重量m体积n的背包最多有放多少件物品。
所以该问题被转换为一个二维的0-1背包问题。
解题思路:
首先理解题意将其转换为0-1背包问题。
其次,此处的动态滚动数组是二维的:
dp[i][j]表示:装满承重i,体积为j的背包最多有多少件物品。
之前的递推公式为:
dp[j]=max(dp[j],dp[j-weight[i]]+values[i])
此处递推公式做些许调整:
dp[i][j]=max(dp[i][j],dp[i-weight[i]][j-vomule[i]]+1)
初始化:
对于背包为0 的物品装满需要0件物品。
1.动态规划:动态滚动数组求解二维0-1背包问题
任然是采用动态规划五部曲来求解该问题,不同之处在于此处的背包是一个二维限制的背包,此处的dp滚动数组是二维的。
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
for(int[] tmp:dp) Arrays.fill(tmp,0);
int countZero=0,countOne=0;
//遍历物品
for(int i=0;i<strs.length;i++){
//计算0/1个数
countZero=0;
countOne=0;
for(char c:strs[i].toCharArray()){
if(c=='0') countZero++;
if(c=='1') countOne++;
}
//遍历m
for(int w=m;w>=0;w--){
//遍历n
for(int v=n;v>=0;v--){
if(countZero<=w&&countOne<=v){
dp[w][v]=Math.max(dp[w][v],dp[w-countZero][v-countOne]+1);
}
}
}
}
return dp[m][n];
}
2.分析
时间复杂度:
O(m×n×str_len)
空间复杂度:文章来源:https://www.toymoban.com/news/detail-798113.html
O(m×n)文章来源地址https://www.toymoban.com/news/detail-798113.html
到了这里,关于Leetcode 474 一和零的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!