Easy to understand Python solutions (Dynamic Programming).


  • 1
    C
    # O(n) space
    def rob1(self, nums):
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        res = [0] * len(nums)
        res[0], res[1] = nums[0], max(nums[0], nums[1])
        for i in xrange(2, len(nums)):
            res[i] = max(nums[i]+res[i-2], res[i-1])
        return res[-1]
    
    def rob2(self, nums):
        if not nums:
            return 0
        res = [0] * len(nums)
        for i in xrange(len(nums)):
            if i == 0:
                res[0] = nums[0]
            elif i == 1:
                res[1] = max(nums[0], nums[1])
            else:
                res[i] = max(nums[i]+res[i-2], res[i-1])
        return res[-1]
      
    # Constant space  
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        a, b = nums[0], max(nums[0], nums[1])
        for i in xrange(2, len(nums)):
            tmp = b
            b = max(nums[i]+a, b)
            a = tmp
        return b

  • 0
    C

    O(1) space solution:

    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        cur = nums[0]
        pre = max(nums[:2])
        for i in xrange(2, len(nums)):
            cur = max(cur+nums[i], pre)
            cur, pre = pre, cur
        return pre

Log in to reply
 

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