力扣 474. 一和零 (另类的0-1背包)

力扣 474. 一和零 (另类的0-1背包)

image.png

image.png

我的想法如下

每次只能从数组里面取一个字符串,计算这个字符串的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];
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注