Ones and Zeroes
给一个字符串组和m,n. 求问里面几个元素可以由m个1和n个0组成. 这个题用dp做, dp[i][j] 表示i个1和j个0组成的string的个数.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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; } } |