Java O(n) Solution - Recursive and Iterative


  • 3

    This one is recursive. The recursive solution is a typical dynamic programing solution with memorization. The helper method maxRobbedMoney return the maximal amount of the money the robber can rob if he start robbing at index "start".

    For example, in order to know the maximal money the robber can rob starting at 0th house, we need to know the maximal amount the robber can rob starting at 2th and 3th house.

    public int rob(int[] nums) {
        Integer[] cache = new Integer[nums.length];
        return Math.max( 
            maxRobbedMoney(nums, cache, 0), 
            maxRobbedMoney(nums, cache, 1) );
    }
    
    public int maxRobbedMoney(int[] nums, Integer[] cache, int start) {
        int len = nums.length;
        if ( start >= len ) { return 0; } 
        
        if ( cache[start] == null ) {
            if ( start >= len-2 ) { 
                cache[start] = nums[start];
            } else {
                int max1 = maxRobbedMoney(nums, cache, start+2);
                int max2 = maxRobbedMoney(nums, cache, start+3);
                cache[start] = nums[start] + Math.max(max1, max2);
            }
        }
        
        return cache[start];
    }   
    

    This solution is iterative. I think the recursive solution is more intuitive but the advantage of this iterative solution is that the space big-O is constant - only three variables are needed.

    For example, right before entering the loop when i = 5, m0 refers to the maximal robbed money if the robber only rob house from 0 to 3; m1 refers to the maximal robbed money if the robber only rob house from 0 to 4. m2, which refers to the maximal robbed money if the robber only rob house from 0 to 5, can be calculated from these two numbers.

    public int rob(int[] nums) {
            
            if ( nums.length == 0 ) { return 0;       }
            if ( nums.length == 1 ) { return nums[0]; }
            
            // m0 is the max at index i-2, m1 at index i-1, m2 at index i-2
            int m0 = nums[0], m1 = Math.max(nums[0],nums[1]), m2;
            
            for ( int i = 2; i < nums.length; i++ ) {
                m2 = Math.max( m0+nums[i], m1 );
                m0 = m1; m1 = m2;
            }
            return m1;
      }

Log in to reply
 

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