Python by employ an extra dp array


  • 0

    In order to exclude the first house, I employed another array dp2 to store all the solution except the first house. This is relatively easy for human understand, but actually using only two variables is totally enough rather than keep tracking of the whole array.

    class Solution(object):
        def rob(self, nums):
            # dp1 nums[0:], dp2 nums[1:]
            # dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]) if i != length - 1 else max(dp1[-2], dp2[ -3] + nums[i])
            if not nums:
                return 0
            if len(nums) <= 2:
                return max(nums)
            dp1, dp2 = [ 0 for i in xrange(len(nums)) ], [ 0 for i in xrange( len(nums) - 1) ]
            for i in xrange(len(nums)):
                dp1[i] = max(nums[:i + 1]) if i <= 1 else max(dp1[i - 1], dp1[i - 2] + nums[i]) 
            for i in xrange(len(nums[1:])):
                dp2[i] = max(nums[1:i + 2]) if i <= 1 else max(dp2[i - 1], dp2[i - 2] + nums[i+1]) 
            dp1[-1] =  max(dp1[-2] , (dp2[-3] if len(dp2) >= 3 else 0) + nums[-1])
            return dp1[-1]
    

Log in to reply
 

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