1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
private Integer[][][] memo;
public int findMaxForm(String[] strs, int m, int n) {
int[][] charCount = new int[strs.length][2];
for (int i = 0; i < charCount.length; i++) {
String currString = strs[i];
int ones = countOne(currString);
int zeroes = currString.length() - ones;
charCount[i][0] = zeroes;
charCount[i][1] = ones;
}
memo = new Integer[strs.length][m + 1][n + 1];
return dfs(charCount, 0, m, n);
}
private int dfs(int[][] charCount, int pos, int remainM, int remainN) {
if (pos == charCount.length) {
return 0;
}
if (memo[pos][remainM][remainN] != null) {
return memo[pos][remainM][remainN];
}
int taken = 0;
if (remainM - charCount[pos][0] >= 0 && remainN - charCount[pos][1] >= 0) {
taken = dfs(charCount, pos + 1, remainM - charCount[pos][0], remainN - charCount[pos][1]) + 1;
}
int notTaken = dfs(charCount, pos + 1, remainM, remainN);
return memo[pos][remainM][remainN] = Math.max(taken, notTaken);
}
private int countOne(String s) {
char[] sArray = s.toCharArray();
int ans = 0;
for (char c : sArray) {
if (c == '1') {
ans += 1;
}
}
return ans;
}
}
|
取不取当下位置要看取完后是否剩下的M和N都大于等于0. 如果一个小于0就说明不能取. 我之前是直接不管就取, 如果出现M小于等于0或者N小于等于0, 直接返回0. 这是不对的. 因为如果一个是0另一个不是0但仍然可以继续往后取啊, 只要不取含有是0的那一个char的string即可. 如果出现M和N小于0, 那一定是上一步取了个什么后到达了这里, 那么我们返回后它那里还会加个1. 但实际不应该 + 1因为上一步去不了, 那这样我们这一步该返回-1, 这样到上一步再加个1就抵消了. 这样看来逻辑就很混乱.
于是我们取之前先看取后是否M和N都大于等于0.
时间复杂度: O(l * m * n)
空间复杂度: O(l * m * n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] charCount = new int[strs.length][2];
for (int i = 0; i < charCount.length; i++) {
String currString = strs[i];
int ones = countOne(currString);
int zeroes = currString.length() - ones;
charCount[i][0] = zeroes;
charCount[i][1] = ones;
}
int[][] memo = new int[m + 1][n + 1];
for (int i = strs.length - 1; i >= 0; i--) {
for (int j = m; j >= 0; j--) {
for (int k = n; k >= 0; k--) {
int taken = 0;
if (j - charCount[i][0] >= 0 && k - charCount[i][1] >= 0) {
taken = memo[j - charCount[i][0]][k - charCount[i][1]] + 1;
}
int notTaken = memo[j][k];
memo[j][k] = Math.max(taken, notTaken);
}
}
}
return memo[m][n];
}
private int countOne(String s) {
char[] sArray = s.toCharArray();
int ans = 0;
for (char c : sArray) {
if (c == '1') {
ans += 1;
}
}
return ans;
}
}
|
根据递归写出来的dp. 3D dp但是可以简化为2D的.
时间复杂度不变.
空间复杂度: O(m * n)
