Java memoization and accepted DP solutions with explanations


  • 4
    Z

    Hi there! I am sharing explanation of my solution. In the problem what matters is the number of zeros and ones in each string. Therefore the first thing we have to do, is to turn the array of string into array of pairs. The ith pair contains number of zeros and ones in ith string. Next step is to determine how many pairs from the array we can cover by m and n;
    The strightforward idea is backtracking. So we can just try out covering strings starting from different positions and maximize the result. Implementation of this idea is written below:

    public class Solution {
        Integer memo[][][];
        public int findMaxForm(String[] strs, int m, int n) {
            if(strs == null || strs.length == 0 || (m == 0 && n == 0)) return 0;
            memo = new Integer[m+1][n+1][strs.length];
            int [][] pairs = new int[strs.length][2];
            for(int i = 0;i<strs.length;i++){
                for(int j = 0;j<strs[i].length();j++){
                    char ch  = strs[i].charAt(j);
                    if(ch == '0') pairs[i][0]++;
                    else pairs[i][1]++;
                }
            }
            return go(pairs, 0, m, n);
        }
        
        public int go(int pairs[][], int s, int m, int n){
            if(s >= pairs.length) return 0;
            if(memo[m][n][s] != null) return memo[m][n][s];
            int count = 0;
            for(int i = s;i<pairs.length;i++){
                int dm = m - pairs[i][0];
                int dn = n - pairs[i][1];
                if(dm >= 0 && dn >=0) {
                    count = Math.max(count, 1+go(pairs, i+1, dm, dn));
                }
            }
            memo[m][n][s] = count;
            return count;
        }
    } 
    
    

    This top to down approach solution gets TLE at 51/56 test. But I think this approach could be accepted in an interview.
    My second solution uses bottom-up algorithm (DP). But pursues the same thinking approach.
    A state of my DP (int i, int numOfZeros, int numOfOnes) describes the maximum number of strings we can construct starting from index 'i' by having numOfZeros zeros and numOfOnes ones.
    There are two simple transition functions from upper state to lower state.

    • First transition is skipping the ith string and just taking the maximum value we can construct starting from i-1 th string.
    • Second transition is constructing current string (ith string) then adding maximum number of strings that can be constructed starting from i-1 th string by the rest of ones and zeros (numOfZeros - pair[i][0] and numOfOnes-pair[i][1]).

    The value for the current state is the maximum of values of the two transaction. Finally the answer is the value of state that describes the number of strings that can be constructed starting from the last(or the first,actually does not matter) index of the input string by m zeros and n ones. In other words just return dp[strs.length-1][m][n];

    public class Solution {
        
        public int findMaxForm(String[] strs, int m, int n) {
            if(strs == null || strs.length == 0 || (m == 0 && n == 0)) return 0;
            int dp [][][] = new int[strs.length][m+1][n+1];
            int [][] pairs = new int[strs.length][2];
            for(int i = 0;i<strs.length;i++){
                for(int j = 0;j<strs[i].length();j++){
                    char ch  = strs[i].charAt(j);
                    if(ch == '0') pairs[i][0]++;
                    else pairs[i][1]++;
                }
            }
            for(int zeros =  pairs[0][0];zeros<=m;zeros++){
                   for(int ones = pairs[0][1];ones<=n;ones++){
                       dp[0][zeros][ones] = 1;
                   }
            } 
            for(int i  = 1;i<strs.length;i++){
               for(int zeros =  0;zeros<=m;zeros++){
                   for(int ones = 0;ones<=n;ones++){
                       dp[i][zeros][ones] = dp[i-1][zeros][ones];
                   }
               }
               for(int zeros =  pairs[i][0];zeros<=m;zeros++){
                   for(int ones = pairs[i][1];ones<=n;ones++){
                       dp[i][zeros][ones] = Math.max(dp[i-1][zeros][ones], 1+dp[i-1][zeros-pairs[i][0]][ones-pairs[i][1]]);
                   }
               }
            }
            return dp[strs.length-1][m][n];
        }
        
       
    }
    
    

    Time and space complexity of the solution is O(n*m*pairs.length)


  • 0
    T

    Good solution, but why do you initialize your dp[][][] from zeros = pairs[0][0], ones = pairs[0][1]?


  • 0
    Z

    @theCodeMonkey.John Good question. In order to be able to construct ith pair, which has pairs[i][0] zeros and pairs[i][1] ones, it is necessary to have at least the same amount of zeros and ones. Thus for the sake of avoiding if statements, I first initialize all states default values (when we skip ith string):

    for(int zeros =  0;zeros<=m;zeros++){
                   for(int ones = 0;ones<=n;ones++){
                       dp[i][zeros][ones] = dp[i-1][zeros][ones];
                   }
     }
    

    After that, I consider two transactions only for pairs of zeros and ones that can cover current string:

    for(int zeros =  pairs[i][0];zeros<=m;zeros++){
                   for(int ones = pairs[i][1];ones<=n;ones++){
                       dp[i][zeros][ones] = Math.max(dp[i-1][zeros][ones], 1+dp[i-1][zeros-pairs[i][0]][ones-pairs[i][1]]);
                   }
     }
    

  • 0
    A

    You can optimize your space complexity till O(m*n). You are using only (i-1)'s state. It is enough to store only previous state's results.


  • 0
    Z

    @amanchik Good point! I know:=)


  • 0

    @ZhassanB Actually, the initial DP setting could be removed if you define dp[0] for first 0 strings instead of strs[0]. Then all entries in dp[0] will be zeros since no string can be formed.

    I am also interested in the top-down recursive solution with with temporary result cached. Here is my version which is TLE with 55/60 tests passed.

    I am thinking the recursive solution with with temporary result cached should calculate fewer dp[i, m, n] entries compared with the bottom-up DP one because actually we do not need to calculate every combination of (m, n) for each i. for example, if strs has only two short words (e.g., "0", "1") and both m and n are huge, then many dp[i, m, n] entries for different (m, n) are useless. The top-down method makes sure to only cache the "useful" ones with a price to pay for the possible O(mnstrs.length) worst memory usage instead of DP's guaranteed O(m*n) memory usage.

    I am not sure why the top-down solution got TLE even with possible fewer calculation (maybe the hashmap overhead is costing too much?) It got TLE on a test case with hugh size strs with only "1"'s and "0"'s, so indeed it does not really save much time, either.

        vector<unordered_map<int, unordered_map<int, int>>> dp; // cache results
        vector<vector<int>> freq;
        int findMaxForm(vector<string>& strs, int n0, int n1) {
          int ns = strs.size(); freq = vector<vector<int>>(ns, vector<int>(2)); dp.resize(ns);
          for (int i = 0; i < ns; ++i) for (char c : strs[i]) freq[i][c-'0'] = freq[i][c-'0']+1;
          return dfs(ns-1, n0, n1);
        }    
        
        int dfs(int i, int c0, int c1) {
          if (i < 0 ) return 0;
          if (dp[i].count(c0) && dp[i][c0].count(c1)) return dp[i][c0][c1];
          dp[i][c0][c1] = dfs(i-1, c0, c1);
          if (c0 >= freq[i][0] && c1 >= freq[i][1])
            dp[i][c0][c1] = max(dp[i][c0][c1], 1 + dfs(i-1, c0-freq[i][0], c1-freq[i][1]));
          return dp[i][c0][c1];
        }
    

Log in to reply
 

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