474. 一和零 (opens new window)

1.动规

背包问题，dp[i][j]表示零的个数为i，一的个数为j的最大子集的大小。采用一维滚动数组更新。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp=new int[m+1][n+1];
        int res=0;
        for(int i=0;i<strs.length;i++){
            int zero=findZero(strs[i]);
            int one=strs[i].length()-zero;
            for(int j=m;j>=0;j--){
                for(int k=n;k>=0;k--){
                    if(j-zero==0&&k-one==0) dp[j][k]=Math.max(dp[j][k],1);
                    if(j-zero>=0&&k-one>=0&&dp[j-zero][k-one]!=0) dp[j][k]=Math.max(dp[j][k],dp[j-zero][k-one]+1);
                    res=Math.max(res,dp[j][k]);
                }
            }
        }
        return res;
    }
    public int findZero(String s){
        int res=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='0') res++;
        }
        return res;
    }
}