力扣 474. 一和零 (另类的0-1背包)
我的想法如下
每次只能从数组里面取一个字符串,计算这个字符串的0的个数和1的个数。
假设有一个背包,每次遍历strs中的字符串,都选择把这个字符串放进背包或者不放进背包。
设dp[i][j]是容量为i个0和j个1的背包所容纳的字符串的最大数目,可推导dp[i][j]=max(dp[i][j], dp[i-numZero][j-numOne],numZero是当前遍历的字符串中0的个数,numOne是当前遍历的字符串的1的个数。
dp[0][0]=0,其他dp[i][j]都初始化成0。
因为i>=numZero且j>=numOne才有意义,所以倒序遍历i和j,i和j的初始值分别是m和n。
这里的二维dp数组相当于经典的0-1背包问题的一维数组形式。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
dp[0][0]=0;
int numZero;
int numOne;
for(int k=0;k<strs.length;k++){
numZero=(int)strs[k].chars().filter(ch->ch=='0').count();
numOne=(int)strs[k].chars().filter(ch->ch=='1').count();
for(int i=m; i>=numZero; i--){
for(int j=n; j>=numOne;j--){
dp[i][j]=Math.max(dp[i][j],dp[i-numZero][j-numOne]+1);
}
}
}
return dp[m][n];
}
}