Recursive solution with map 2ms


  • 0
    A

    HashMap<Integer,Integer> map = new HashMap<>();

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        map.put(nums.length,0);
        return rob(nums,0);
    }
    
    private int rob(int[] nums, int idx){
        if (map.containsKey(idx)) return map.get(idx);
        
        int max;
        if (nums.length - idx == 1){
            max = nums[nums.length-1];
            map.put (idx,max);
        }
        else if (nums.length - idx == 2){
            max = Math.max(nums[nums.length-1],nums[nums.length-2]);
            map.put(idx,max);
        }
        else {
            max =  Math.max(nums[idx] + rob(nums,idx + 2), nums[idx+1] + rob(nums,idx + 3));
            map.put(idx,max);
        }
        return max;
    }

Log in to reply
 

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