A simple Python slution


  • 4
    L
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def rob(self, num):
            left = left_left = 0
            for i in xrange(len(num)):
                left, left_left =  max(num[i] + left_left, left), left
            return left

  • 3
    B

    This is mine, the classic DP , more complicate than yours:

    def rob(self, num):
        if len(num)==0:
            return 0
        r=[0 for i in range(len(num))]
        for i in range(len(num)):
            if i==0: 
                r[0]=num[0]
            elif i==1: 
                r[1]=max(num[0], num[1] )
            else:
                r[i]=max(r[i-1], r[i-2]+num[i] )
        return r[len(num)-1]
    

  • 0
    L

    we only need two memarization.


  • 0
    L

    DP, similar to bearstand's solution

    def rob(self, nums):
        if len(nums) <= 0:
            return 0
        elif len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0],nums[1])
        else :
            arr = [0]*len(nums)
            arr[0] = nums[0]
            arr[1] = max(nums[0],nums[1])
            for i in range(2,len(nums)) :
                arr[i] = max(arr[i-2] + nums[i], arr[i-1])
    
            return arr[len(nums)-1]

Log in to reply
 

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