题目地址：

https://www.lintcode.com/problem/ones-and-zeroes/description

给定一个$0-1$字符串组成的数组$A$，再给两个非负整数$m$和$n$，问用$m$个$0$和$n$个$1$最多能组成出多少个$A$中的字符串。

思路是动态规划。设$f[k][i][j]$表示在有$i$个$0$和$j$个$1$的情况下，能组成多少个$A[0:k]$中的字符串。那么组成字符串的方案可以分为两类： 1、不去组成$A[k]$，那么此时答案就是$f[k-1][i][j]$； 2、组成$A[k]$，那么就需要消耗若干个$0$和$1$，假设$A[k]$有$x$个$0$和$y$个$1$，那么此时答案就是$1+f[k-1][i-x][j-y]$，当然这时候需要$i\ge x$并且$j\ge y$。 所以有：$$f[k][i][j]=\max \{f[k-1][i][j],1+f[k-1][i-x][j-y]\}$$初始条件，当$i$个$0$和$j$个$1$能够组成$A[0]$的时候，$f[0][i][j]=1$，否则$f[0][i][j]=0$。代码如下：

public class Solution { /** * @param strs: an array with strings include only 0 and 1 * @param m: An integer * @param n: An integer * @return: find the maximum number of strings */ public int findMaxForm(String[] strs, int m, int n) { // write your code here if (strs == null || strs.length == 0) { return 0; } // 用两个数组来保存strs[i]含的0的个数以及1的个数 int[] zcount = new int[strs.length], ocount = new int[strs.length]; for (int i = 0; i < strs.length; i++) { for (int j = 0; j < strs[i].length(); j++) { if (strs[i].charAt(j) == '0') { zcount[i]++; } else { ocount[i]++; } } } int[][][] dp = new int[strs.length][m + 1][n + 1]; for (int k = 0; k < strs.length; k++) { for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (k == 0) { dp[k][i][j] = i >= zcount[0] && j >= ocount[0] ? 1 : 0; } else { dp[k][i][j] = dp[k - 1][i][j]; if (i >= zcount[k] && j >= ocount[k]) { dp[k][i][j] = Math.max(dp[k][i][j], 1 + dp[k - 1][i - zcount[k]][j - ocount[k]]); } } } } } return dp[strs.length - 1][m][n]; } }

时空复杂度$O(l_{A}mn)$。

空间优化的话，可以类似滚动数组的办法，这里用滚动平面。代码如下：

public class Solution { /** * @param strs: an array with strings include only 0 and 1 * @param m: An integer * @param n: An integer * @return: find the maximum number of strings */ public int findMaxForm(String[] strs, int m, int n) { // write your code here if (strs == null || strs.length == 0) { return 0; } int[] zcount = new int[strs.length], ocount = new int[strs.length]; for (int i = 0; i < strs.length; i++) { for (int j = 0; j < strs[i].length(); j++) { if (strs[i].charAt(j) == '0') { zcount[i]++; } else { ocount[i]++; } } } int[][][] dp = new int[2][m + 1][n + 1]; for (int k = 0; k < strs.length; k++) { for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (k == 0) { dp[k][i][j] = i >= zcount[0] && j >= ocount[0] ? 1 : 0; } else { dp[k & 1][i][j] = dp[k - 1 & 1][i][j]; if (i >= zcount[k] && j >= ocount[k]) { dp[k & 1][i][j] = Math.max(dp[k & 1][i][j], 1 + dp[k - 1 & 1][i - zcount[k]][j - ocount[k]]); } } } } } return dp[strs.length - 1 & 1][m][n]; } }

时间复杂度不变，空间$O(mn)$。