Leetcode: House Robber
1 min readDec 26, 2016
This is a typical dynamic programming question. Suppose we know the solution for first n houses, now to find the solution for nth house
- We can either rob the nth house
- 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]