LC198 - House Robber

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Note: Robbing every other house is not always the best strategy, because 2 non 1-spaced houses might contain more loot than 3 1-spaced houses.

Solution

Naive

The naive solution is to visit each node of the decision tree to get the maximum loot of each path. Time complexity of this solution is $O(2^n)$, which is not ideal.

Dynamic Programming

We break the problem down into subproblems, which is to rob the first house and the remaining subarray of houses, or the subarray starting from the second house. Time complexity of this solution is $O(n)$, and no extra space is used so $O(1)$ space.

def rob(self, nums: List[int]) -> int:
	rob1 = 0
	rob2 = 0
	
	for n in nums:
		maxRob = max(n + rob1, rob2)
		rob1 = rob2
		rob2 = maxRob
	
	return maxRob