Ones and Zeroes
给一个字符串组和m,n. 求问里面几个元素可以由m个1和n个0组成. 这个题用dp做, dp[i][j] 表示i个1和j个0组成的string的个数.
public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(String s : strs) {
int[] c = count(s);
for(int i = m ; i >= c[0]; i--) {
for(int j = n; j >= c[1]; j--) {
dp[i][j] = Math.max(dp[i][j], 1 + dp[i-c[0]][j-c[1]]);
}
}
}
return dp[m][n];
}
public int[] count(String s) {
int[] c = new int[2];
for(int i = 0 ; i < s.length(); i++) {
c[s.charAt(i)-'0']++;
}
return c;
}
}