# Evolve from brute force to dp

1. O(2^k), try all the combinations.
``````    int findMaxForm(vector<string>& strs, int m, int n) {
int sz = strs.size();
vector<pair<int,int>> ct(sz);
for(int i=0;i<sz;i++) {
int sn = strs[i].size(), z=0;
for(char c:strs[i]) if(c=='0') z++;
ct[i]=pair<int,int>(z,sn-z);
}
return dfs(0,m,n,ct);
}
int dfs(int p, int m, int n, vector<pair<int,int>>& ct) {
if(m<0 || n<0) return -1;
if(p==ct.size()) return 0;
return max(dfs(p+1,m,n,ct), 1+dfs(p+1,m-ct[p].first,n-ct[p].second,ct));
}
``````
1. O(kmn) memoization and dp O(kmn) space
``````    int findMaxForm(vector<string>& strs, int m, int n) {
int sz = strs.size();
vector<pair<int,int>> ct(sz);
for(int i=0;i<sz;i++) {
int sn = strs[i].size(), z=0;
for(char c:strs[i]) if(c=='0') z++;
ct[i]=pair<int,int>(z,sn-z);
}
vector<vector<vector<int>>> mem(sz,vector<vector<int>>(m+1,vector<int>(n+1,-1)));
return dfs(0,m,n,ct,mem);
}
int dfs(int p, int m, int n, vector<pair<int,int>>& ct,vector<vector<vector<int>>>& mem) {
if(m<0 || n<0) return -1;
if(p==ct.size()) return 0;
if(mem[p][m][n]>-1) return mem[p][m][n];
return mem[p][m][n]=max(dfs(p+1,m,n,ct,mem), 1+dfs(p+1,m-ct[p].first,n-ct[p].second,ct,mem));
}
int findMaxForm(vector<string>& strs, int m, int n) {
int sz = strs.size();
vector<vector<vector<int>>> mem(sz+1,vector<vector<int>>(m+1,vector<int>(n+1)));
for(int i=sz-1;i>=0;i--) {
int z=count(strs[i].begin(),strs[i].end(),'0');
for(int j=0;j<=m;j++)
for(int k=0;k<=n;k++)
mem[i][j][k] = j>=z&& k>= strs[i].size()-z ?
max(mem[i+1][j][k], 1+mem[i+1][j-z][k-strs[i].size()+z]) : mem[i+1][j][k];
}
return mem[0][m][n];
}
``````
1. O(mn) space dp. In the above dp solution, the current state i only depends on state i+1, this means we only need to cache two states of i. In fact, we only need to cache 1 state of i by updating from m, n to 0. Because the we need the m-zero, n-one state value from the previous state. The great idea is from @yangluphil.
``````    int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> mem(m+1,vector<int>(n+1));
for(string &s:strs) {
int z=count(s.begin(),s.end(),'0');
for(int i=m;i>=z;i--)
for(int j=n;j>=(int)s.size()-z;j--)
mem[i][j] = max(mem[i][j], 1+mem[i-z][j-s.size()+z]);
}
return mem[m][n];
}
``````

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