Python solution with detailed explanation


  • 0
    G

    Solution with discussionhttps://discuss.leetcode.com/topic/80721/python-solution-with-detailed-explanation

    House Robber II https://leetcode.com/problems/house-robber-ii/?tab=Description

    Memoization:

    • Use another variable first which indicates if first house is included or not in the current DFS path.
    • Based on first, at index N-1, we will set use (the case where we rob a house) to 0 or nums[i].
    • Caching will be 2D. At index i, we now ask what is the maximum money we can rob given we robbed house 0 or not.
    class Solution(object):
        def helper(self, i, nums, cache, first):
            N = len(nums)
            if i >= N:
                return 0
            if i in cache and first in cache[i]:
                return cache[i][first]
            cache.setdefault(i, {})
            if i == 0:
                use, not_use = nums[i]+self.helper(i+2, nums, cache, True), self.helper(i+1, nums, cache, False)
            elif i + 1 == N and first:
                use, not_use = 0, self.helper(i+1, nums, cache, first)
            else:
                use, not_use = nums[i]+self.helper(i+2, nums, cache, first), self.helper(i+1, nums, cache, first)
            cache[i][first] = max(use, not_use)
            return cache[i][first]
        
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            cache = {}
            return self.helper(0, nums, cache, False)
    

    Dynamic Programming

    class Solution(object):
        def sub_rob(self, nums, lo, hi):
            """
            :type nums: List[int]
            :rtype: int
            """
            result = prev_prev = prev = 0
            for idx in range(lo, hi+1):
                result = max(prev_prev+nums[idx], prev)
                prev_prev = prev
                prev = result
            return result    
        
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) < 2:
                return sum(nums)
            return max(
                            self.sub_rob(nums, 0, len(nums)-2),
                            self.sub_rob(nums, 1, len(nums)-1)
                       )
    

Log in to reply
 

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