Sharing of my solution using two-pass DP


  • 0
    R
    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def rob(self, nums):
            if not nums:
                return 0
            l=len(nums)
            if l==1:
                return nums[0]
            DP=[[0 for j in range(2)] for i in range(l)]
    
            #make sure the first house un-robbed
            DP[l-1][0]=nums[l-1]
            for i in range(l-2,0,-1):
                DP[i][0]=max(DP[i][0],DP[i+1][0])
                if i+2<l:
                    DP[i][0]=max(DP[i][0],DP[i+2][0]+nums[i])
            DP[0][0]=DP[1][0]
            #make sure the last house un-robbed
            DP[l-2][1]=nums[l-2]
            for i in range(l-3,-1,-1):
                DP[i][1]=max(DP[i][1],DP[i+1][1])
                if i+2<l:
                    DP[i][1]=max(DP[i][1],DP[i+2][1]+nums[i])
            return max(DP[0][0],DP[0][1])
    if __name__=="__main__":
        s=Solution()
        case=[[1,1,1]]
        print s.rob(*case)
        case=[[2,1]]
        print s.rob(*case)

Log in to reply
 

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