Simple Python Solution with Explanation


  • 0
    W

    DP idea:
    f(j): max money when arriving at house j (after deciding robbing it or not)
    f(j) = max(f(j-2)+a[j], f(j-1))

    class Solution(object):
        def rob(self, nums):
           
            ll = len(nums)
            if ll == 0:
                return 0
            
            res = []
            for i in range(ll):
                if i == 0:
                    res.append(nums[i])
                elif i == 1:
                    res.append(max(nums[i-1], nums[i]))
                else:
                    temp = max(res[-1], res[-2] + nums[i])
                    res.append(temp)
    
            return res[-1]

Log in to reply
 

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