Very simple O(n) time O(n) space dp solution with explanation in Java


  • 0
    T
    public class Solution {
        public int rob(int[] nums) {
            if(nums.length==0) return 0;
            int[] maxLoot = new int[nums.length];
            maxLoot[0] = nums[0]; //if there was only one house to loot
            if(nums.length == 1) return maxLoot[0];
            maxLoot[1] = Math.max(nums[0],nums[1]); //if there were only 2 houses to loot, choose the one with max money.
            
            for(int i = 2;i<nums.length;i++){
                // when deciding whether to loot the i'th house or not:
                /*
                  1. If picking the i'th house, consider maxLoot[i-2] which is the loot gathered until the i-2nd house + i'th house OR.
                  2. If not picking the i'th house, consider the loot gathered till the previous house which is maxLoot[i-1].
                  
                  Pick whichever is maximum.
                */
                maxLoot[i] = Math.max(maxLoot[i-2]+nums[i], maxLoot[i-1]);    
            }
            
            return maxLoot[nums.length-1];
        }
    }
    

Log in to reply
 

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