Evolve from brute force to dp


  • 0
    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];
        }
    

Log in to reply
 

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