Python solution based on House Robber


  • 0
    T
    class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        if not nums:
            return 0
        return max(self._rob(nums[1:]), nums[0] + self._rob(nums[2:-1]))
    
    def _rob(self, nums):
        prev_no = prev_yes = 0
        for n in nums:
            temp = prev_no
            prev_no = max(prev_no, prev_yes)
            prev_yes = temp + n
        return max(prev_no, prev_yes)
    

    There are two cases,

    if we do not rob house[0], we can rob nums[1:]

    else we can rob nums[2:-1]


  • 0
    W

    Same as my thought, but I cannot understand why you define a sub-function? Is it faster?

    BTW my code is like this(40ms):

    class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        if not nums:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        if len(nums) == 2:
            return max(nums[0], nums[1])
        
        dp = {}
        dpw0 = {}
        
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        dpw0[0], dpw0[1] = 0, nums[1]
        
        
        for i in range(2, len(nums) - 1):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
            dpw0[i] = max(dpw0[i - 2] + nums[i], dpw0[i - 1])
        dpw0[len(nums) - 1] = max(dpw0[len(nums) - 3] + nums[len(nums) - 1], dpw0[len(nums) - 2])
        
        return max(dp[len(nums) - 2], dpw0[len(nums) - 1])
    

Log in to reply
 

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