https://leetcode-cn.com/problems/ones-and-zeroes/
动态规划。
用dp[i][j][k]表示前i个字符串中 j个0、k个1的最大子集大小 。下标均从1开始计数。
当i=0时,没有字符串,所以dp[i][j][k]=0。
转移方程
这个字符串的0和1个数分别为zeros,ones.
1.j>=zeros&&k>=ones
(1)向子集中加入这个字符串
dp[i][j][k]=dp[i-1][j-zeros][k-ones]+1
(2)不向子集中加入
dp[i][j][k]=dp[i-1][j][k]
综上,dp[i][j][k]=min(dp[i-1][j-zeros][k-ones]+1,dp[i][j][k]=dp[i-1][j][k]);
2.else
dp[i][j][k]=dp[i-1][j][k]
class Solution { public int findMaxForm(String[] strs, int m, int n) { int len=strs.length; if(len==0) return 0; int[][][] dp=new int[len+1][m+1][n+1]; /* for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ dp[0][j][k]=0; } } */ for(int i=1;i<=len;i++){ int zeros=count(strs[i-1]); int ones=strs[i-1].length()-zeros; for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ dp[i][j][k]=dp[i-1][j][k]; if(j>=zeros&&k>=ones){ dp[i][j][k]=Math.max(dp[i-1][j-zeros][k-ones]+1,dp[i][j][k]); } } } } return dp[len][m][n]; } //统计0的个数 public int count(String s){ int count=0; for(char c:s.toCharArray()){ if(c=='0'){ count++; } } return count; } }
时间复杂度:O(lmn+L),其中 l 是数组 strs 的长度,m 和 n 分别是 0 和 1 的容量,L 是数组 strs 中的所有字符串的长度之和。
空间复杂度 O(lmn)
空间复杂度:O(mn),其中 m 和 n 分别是 0 和 1 的容量。使用空间优化的实现,需要创建 m+1 行 n+1 列的二维数组dp。
由于dp[i][][] 的每个元素值的计算只和dp[i−1][][] 的元素值有关,因此可以使用滚动数组的方式,去掉 dp 的第一个维度,将空间复杂度优化到 O(mn)。
实现时,内层循环需采用倒序遍历的方式,这种方式保证转移来的是dp[i−1][][] 中的元素值。
public int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; int length = strs.length; for (int i = 0; i < length; i++) { int[] zerosOnes = getZerosOnes(strs[i]); int zeros = zerosOnes[0], ones = zerosOnes[1]; for (int j = m; j >= zeros; j--) { for (int k = n; k >= ones; k--) { dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1); } } } return dp[m][n]; }