# 7-line DP solution time O(m*n*strs.length) (detailed explanation)

• ``````    int findMaxForm(vector<string>& strs, int n0, int n1) {
vector<vector<int>> dp(n0+1, vector<int>(n1+1)); // dp[i][j] = results if using i 0's and j 1's
for (auto &s : strs) {
vector<int> freq(2); for (char c : s) ++freq[c-'0']; // 0's and 1's frequency in s
for (int num0 = n0; num0 >= freq[0]; --num0)
for (int num1 = n1; num1 >= freq[1]; --num1)
dp[num0][num1] = max(dp[num0][num1], 1 + dp[num0 - freq[0]][num1 - freq[1]]);
}
return dp[n0][n1];
}
``````

Key observation: Let `dp(n0, n1, k)` be the max number of strings which could be formed by using `n0` 0's and `n1` 1's in the first `k` strings of the given string array, then we have

• initial condition: `dp(n0, n1, 0) = 0` for any `n0`, `n1`,
• boundary condition: `dp(n0, n1, k) = 0` for any `n0 < 0` or `n1 < 0`,
• recursion: `dp(n0, n1, k) = max( dp(n0, n1, k-1), 1+dp(n0-freq[k-1][0], n1-freq[k-1][1], k-1) )`,

where `freq[k-1][0], freq[k-1][1]` are frequencies of char `'0'` and `'1'` in the `k`th string.

The recursion means that if we try to form first `k` strings with `n0` 0's and `n1` 1's, there are only two cases:

1. The `k`th string is not formed, so the max number of formed strings is same as using only first `k-1` strings;
2. Otherwise, we have used `freq[k-1][0]` 0's and `freq[k-1][1]` 1's to form the `k`th string, and so with `n0 - freq[k-1][0]` 0's and `n1 - freq[k-1][1]` 1's left to form first `k-1` strings.

The result of `dp(n0, n1, k)` is whichever case 1 and case 2 has the larger number of strings formed.

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