# Java DFS+Cache, transfer to DP O(mn) space

• DFS + Cache:

public class Solution {
int[][][] cache;
public int findMaxForm(String[] strs, int m, int n) {
cache = new int[strs.length][m + 1][n + 1];
return search(0, m, n, strs);
}
private int search(int pos, int m, int n, String[] strs) {
if (m < 0 || n < 0) return -1;
if (pos > strs.length - 1) return 0;
if (cache[pos][m][n] != 0) return cache[pos][m][n] == -1 ? 0 : cache[pos][m][n];

int x = 0, y = 0;
for (int i = 0; i < strs[pos].length(); i++) {
if (strs[pos].charAt(i) == '0') x++;
else y++;
}
int ret = Math.max(search(pos + 1, m - x, n - y, strs) + 1, search(pos + 1, m, n, strs));
if (ret == 0) cache[pos][m][n] = -1;
else cache[pos][m][n] = ret;
return ret;
}
}

DP:

public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][][] F = new int[2][m + 1][n + 1];

for (int pos = strs.length - 1; pos >= 0; pos--) {
int x = 0, y = 0;
for (int i = 0; i < strs[pos].length(); i++) {
if (strs[pos].charAt(i) == '0') x++;
else y++;
}

for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i - x < 0 || j - y < 0) {
F[pos % 2][i][j] = F[(pos + 1) % 2][i][j];
} else {
F[pos % 2][i][j] = Math.max(F[(pos + 1) % 2][i - x][j - y] + 1, F[(pos + 1) % 2][i][j]);
}
}
}
}
return F[0][m][n];
}
}

• Did this get AC?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.