Leetcode: House Robber

House Robber | LeetCode OJ

This is a typical dynamic programming question. Suppose we know the solution for first n houses, now to find the solution for nth house

1. We can either rob the nth house
2. We can leave the nth house

If we rob the nth house we can use the solution of n-2th house and add amount in nth house to it.

If we do not want to rob this house we can just use the solution for n-1th house. Suppose we have [4,1,1,4,5] as input. We can start from left and use the above concept to fill the table. At each step we compare 2 values, first is for robbing the current house and next is for leaving the current house.

from collections import defaultdict

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = defaultdict(int)
        for i in range(len(nums), 0, -1):
            dp[i] = max(nums[i - 1] + dp[i + 2], dp[i + 1])
        return dp[1]