題意理解：
????????給你一個二進制字符串數(shù)組?
strs?和兩個整數(shù)?m?和?n?。????????請你找出并返回?
strs?的最大子集的長度，該子集中?最多?有?m?個?0?和?n?個?1?。????????如果?
x?的所有元素也是?y?的元素，集合?x?是集合?y?的?子集?。? ? ? ??
? ? ? ? 將字符串0和1的個數(shù)看作是該字符串的兩個維度，假設將其看作物品的重量和體積。
? ? ? ? 那么m和n就是對背包的限制：承重量為m, 體積為的背包。
? ? ? ? 求元素最多的子集，該問題可以轉換為：求裝滿承重量m體積n的背包最多有放多少件物品。
? ? ? ? 所以該問題被轉換為一個二維的0-1背包問題。
解題思路：
? ? ? ? 首先理解題意將其轉換為0-1背包問題。
? ? ? ? 其次，此處的動態(tài)滾動數(shù)組是二維的：
????????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.動態(tài)規(guī)劃：動態(tài)滾動數(shù)組求解二維0-1背包問題
任然是采用動態(tài)規(guī)劃五部曲來求解該問題，不同之處在于此處的背包是一個二維限制的背包，此處的dp滾動數(shù)組是二維的。
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個數(shù)
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)
空間復雜度：文章來源：http://www.zghlxwxcb.cn/news/detail-798113.html
? ? ? ? O(m×n)文章來源地址http://www.zghlxwxcb.cn/news/detail-798113.html
到了這里，關于Leetcode 474 一和零的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
