Python simple solution


  • 3

    You can just skip 1 house, or 2 houses to get the maximum money.
    That means maximum_money(i_th) = max(maximum_money(i-2th), maximum_money(i-3th)).

    class Solution(object):
        def rob(self, nums):
            leng = len(nums)
            if leng == 0:
                return 0
            elif leng == 1:
                return nums[0]
            elif leng == 2:
                return max(nums[0], nums[1])
                
            money = [0] * leng
            # set initial state
            money[0] = nums[0]
            money[1] = nums[1]
            money[2] = nums[0] + nums[2]
            
            # set the bigger one
            for i in range(3, leng):
                money[i] = max(money[i-2] + nums[i], money[i-3] + nums[i])
            
            return max(money[leng-1], money[leng-2])

  • 0
    M

    simple but nice


  • 0
    H
    class Solution(object):
        def rob(self, nums):
            n = len(nums)
            k = n/2
            if n == 0:
                return 0
            if n == 1:
                return nums[0]
            else: 
                return max(self.rob(nums[0:k])+self.rob(nums[k+1:]), self.rob(nums[:k-1])+self.rob(nums[k:]))

Log in to reply
 

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