# Crack the house robber problem

My previous post introduced the **Knapsack** problem. It states how to solve using the dynamic programming algorithm. Besides **Knapsack**, there’s one series of problems that you might encounter in a coding interview: the house robber problems. Today, let’s talk about it.

**Problem description**

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 system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonightwithout alerting the police.

**Examples:**

Case 1:Input:nums = [1,2,3,1]Output:4Explanation:Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.Case 2:Input:nums = [2,7,9,3,1]Output:12Explanation:Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).

Total amount you can rob = 2 + 9 + 1 = 12.

From the description and examples, we know the robber has to find out the maximum profit for the given houses without stealing two adjacent houses. How to solve it?

## Solution

It seems complicated at the first glance. In fact, if we break it into subproblems, there are only two scenarios to consider: at the current house, will the robber rob it? There are two cases to consider:

- At house
`i`

, if the robber robs it, meaning that the robber didn’t rob the previous house`i-1`

, the maximum profit could be profit at the house`i-2`

plus current house value`i`

- At house
`i`

, if the robber doesn’t rob it, meaning that the previous house`i-1`

could be robbed, the maximum profit might happen at the house`i-1`

As the result, at house `i`

, the maximum profit is determined by its previous houses: `profit[i] = max(profit[i-2]+house[i], profit[i-1])`

. To compare these two values, the best way is to create an array to store the profit.

Let’s take one example to walk through the process:

Input:nums = [2,7,9,3,1]Step 1:

Let's create an array to store the maximum proit the robber robbed. Let's set initial profits all to 0: profit = [0,0,0,0,0,0]. Note that we increate the profit size by 1, it means when i = 0, the profit is zero due to theNonehouse value.Step 2:Initial state is that when i = 0, profit[0] = 0. When i = 1, profit[1] = nums[0] = 2 because it's the maximum profit if we only go over one house. Now profit=[0,2,0,0,0,0]Step 3:Start with index = 2, let's find the maximum profit while iterating the houses.When i = 2, current house value is 7, consider two cases here:

* rob it: profit[2] = profit[2-2] + 7 = 7

* not rob it: profit[2] = profit[2-1] = 2

Obviously, 7 is bigger, profit=[0,2,7,0,0,0]Step 4:Move to index = 3, current house value is 9, consider two cases here:

* rob it: profit[3] = profit[3-2] + 9 = 11

* not rob it: profit[3] = profit[3-1] = 7

Obviously, 11 is bigger, profit=[0,2,7,11,0,0]Step 5:Move to index = 4, current house value is 3, consider two cases here:

* rob it: profit[4] = profit[4-2] + 3= 10

* not rob it: profit[4] = profit[4-1] = 11

Obviously, 11 is bigger, profit=[0,2,7,11,11,0]Step 5:Move to the last house index = 5, current house value is 1, consider two cases here:

* rob it: profit[5] = profit[5-2] + 1 = 12

* not rob it: profit[5] = profit[5-1] = 11

Obviously, 12 is bigger, profit=[0,2,7,11,11,12]Step 6:Now, we've seen all given houses: profit=[0,2,7,11,11,12]. The maximum profit is 12.

**Code:**

` `**def rob(nums):**

if not nums or len(nums) == 0:

return 0

res = nums[0]

profit = [0] * (len(nums) + 1)

profit[1] = nums[0]

for i in range(2, len(profit)):

profit[i] = max(nums[i-1] + profit[i-2], profit[i-1])

res = max(res, profit[i])

return res

**Analysis:**

Let `n`

be the number of the given houses:

- Time complexity:
`O(n)`

since we iterate the`nums`

once, and saved the result at an array. - Space complexity:
`O(n)`

since we create an extra array with size`n+1`

to help to find the maximum profit.

## House Robber II

There’s a more challenging version of the house robber problem:

**Description:**

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place arearranged in a circle.That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, andit will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers

numsrepresenting the amount of money of each house, return the maximum amount of money you can rob tonightwithout alerting the police.

**Examples:**

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

Input:Output:3Explanation:You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.Case 2:nums = [1,2,3,1]

Input:Output:4Explanation:Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

**Solution**

When the houses are circular, it’s different from the previous problem because the first house and last house can’t be robbed at the same time. How to solve it?

In fact, we can divide it into two subproblems:

- Don’t rob the
**first**house, what’s the maximum profit robbed? - Don’t rob the
**last**house, what’s the maximum profit robbed?

Each subproblem could be solved using the previous algorithm. The only part that needs to change is that for the **don’t rob front case: profit[1] = 0**. To record the maximum profit of two different cases, we’ll create two different arrays: `notRobFront`

, and `notRobTail`

. After iterating the houses, we’ll compare two arrays to find the maximum profit.

**Code:**

def rob(nums):

size = len(nums) notRobFront = [0] * (size + 1)

notRobTail = [0] * (size + 1) notRobFront[1] = 0

notRobTail[1] = nums[0] for i in range(2, size):

notRobFront[i] = max(notRobFront[i-1], notRobFront[i-2]+nums[i-1])

notRobTail[i] = max(notRobTail[i-1], notRobTail[i-2]+nums[i-1]) notRobFront[-1] = max(notRobFront[size-1], notRobFront[size-2] + nums[-1]) return max(notRobFront[-1], notRobTail[-2])

**Analysis:**

Let `n`

be the number of the given houses:

- Time complexity:
`O(n)`

since we iterate the`nums`

once, and saved the result at an array. - Space complexity:
`O(2n) ≈ O(n)`

since we create two extra arrays with size`n+1`

to help to find the maximum profit.

Thanks for reading!