Python DP solution, single pass, runs in 32 ms

  • 0

    I am keeping two arrays and instead solve this in one pass. One array solves the problem assuming the first house was robbed (hence the last house cannot) and the other assumes the first house was not robbed (hence the last house can either be robbed or not).

    class Solution(object):
        def rob(self, nums):
            :type nums: List[int]
            :rtype: int
            if not nums: return 0
            if len(nums) == 1: return nums[0]
            if len(nums) == 2: return max(nums[0],nums[1])
            n = len(nums)
            M, N = [[0]*n,[0]*n], [[0]*n,[0]*n]
            M[1][0] = M[0][1] = M[1][1] = nums[0]
            N[1][1] = nums[1]
            for j in range(2,n):
                M[1][j] = max(M[0][j-1], max(M[0][j-2], M[1][j-2])) + nums[j]
                M[0][j] = max(M[0][j-1], M[1][j-1])
                N[1][j] = max(N[0][j-1], max(N[0][j-2], N[1][j-2])) + nums[j]
                N[0][j] = max(N[0][j-1], N[1][j-1])
            return max(M[0][n-1],N[0][n-1],N[1][n-1])

Log in to reply

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