Python solution with detailed explanation


  • 1
    G

    Solution

    House Robber https://leetcode.com/problems/house-robber/

    • At each house, we have the option to either rob the house or not rob the house. This is the single most important insight we shall use while we develop our algorithm. We use this insight in both memoization and dynamic programming approach. In the former we move forward and in the latter we move backwards.

    Memoization:

    • Sketch the recursion tree & go top down. Decide at last node.
    • rob(i) = max(rob_this_house, do_not_rob_this_house)
    • rob(i) = max(nums[i]+rob(i+2), rob(i+1))
    • rob(i) = 0 when we have i >= N - Base Base
    class Solution(object):
        def helper(self, i, nums, cache):
            N = len(nums)
            if i >= N:
                return 0
            if i in cache:
                return cache[i]
            cache[i] = max(nums[i]+self.helper(i+2, nums, cache), self.helper(i+1, nums, cache))
            return cache[i]
        
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return self.helper(0, nums, {})
    

    Table Filling Dynamic Programming

    • Bottom up.
    • rob(i) - Maximum money we can make by robbing houses from [0,1,2..i]
    • rob(i) = max(nums[i] + rob(i-2), rob(i-1)) : rob house(i) or not
    • rob(i) = 0 for i = -1 or -2
    • Move backwards. Assume we have solved the problem till house i-1. Then at house i ask the question - should we rob house i or not?
    • We only need constant space in this case.
    class Solution(object):
        def rob(self, nums):
            result = prev_prev = prev = 0
            for idx in range(len(nums)):
                result = max(prev_prev+nums[idx], prev)
                prev_prev = prev
                prev = result
            return result
    

Log in to reply
 

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