# Java DP solution with explanation

• The idea is to build up the solution for 0..m zeros and 0..n ones, from only knowing 1 string, 2 strings, ..., up to n strings.

For example, for array = {"10", "0", "1"}, m = 1, n = 1.

• for first string "10":
• zero = 0, one = 0
• zero = 1, one = 0
• zero = 0, one = 1
• zero = 1, one = 1, can form "10" [+1]
• continue on the second string "0", with previous knowledge of string "10":
• zero = 0, one = 0
• zero = 1, one = 0, can form "0" [+1]
• zero = 0, one = 1
• zero = 1, one = 1, can form "0" [+1] or 1 string ("10"), known from previous string
• continue on the last string "1", with previous knowledge of strings "10" and "0":
• zero = 0, one = 0
• zero = 1, one = 0, can't form "1", but we know it can form 1 string ("0") from previous set of strings
• zero = 0, one = 1, can form "1" (+1)
• zero = 1, one = 1, (can form "1" and 1 more string ("0") with zero = 1, one = 0, known from previous set of strings) or (1 string ("10"), known from previous set of strings)

Hence, at the end, we know that with zero = 1, one = 1, with string "10", "0", and "1", the maximum number of strings we can form is 2.

``````public int findMaxForm(String[] strs, int m, int n) {
int[][] max = new int[m + 1][n + 1];
for (int i = 0; i < strs.length; i++) {
String str = strs[i];

int neededZero = 0;
int neededOne = 0;
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '0') {
neededZero++;
} else {
neededOne++;
}
}

int[][] newMax = new int[m + 1][n + 1];

for (int zero = 0; zero <= m; zero++) {
for (int one = 0; one <= n; one++) {
if (zero >= neededZero && one >= neededOne) {
int zeroLeft = zero - neededZero;
int oneLeft = one - neededOne;
newMax[zero][one] = Math.max(1 + max[zeroLeft][oneLeft], max[zero][one]);
} else {
newMax[zero][one] = max[zero][one];
}
}
}

max = newMax;
}
return max[m][n];
}
``````

• can you give your explanation?

• @cainiaofei I've added some description to my approach above. Hope it's helpful.

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