Home » Interview coding problems/challenges

# House Robber Problem With Solution

In this article, we are going to see **how to solve the house robber problem which is a famous dynamic problem to start with**? This has been also featured in Amazon interview rounds.
By Radib Kar Last updated : April 21, 2024

## Problem statement

A professional robber is planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping him from robbing each of them is that adjacent houses have security system connected and **it 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 he can rob tonight **without alerting the police**.

## Solution of House Robber Problem

### Example

Input: [1,2,3,1] Output: 4 Explanation: Option 1: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount he can rob = 1 + 3 = 4. Option 2: Rob house 2 (money = 2) and then rob house 4 (money = 1). Total amount he can rob = 2 + 1 = 3 So, option 1 maximizes the money stolen.

### Algorithm

The problem can be cut down to sub-problem of finding whether to rob from i^{th} house or not.

Let f(i)=amount of money stolen after robbing house i

Now, in case of taking decision whether to rob from **i ^{th}** house or not, it completely depends on where the money maximizes. Since, adjacent houses are connected, the robber can't rob two adjacent house. Either he can rob from

**(i-1)**house or he can rob from

^{th}**i**house after robbing from

^{th}**(i-2)**house. To maximize the money simply find which results in maximum amount. In terms of recursive relation we can write,

^{th}f(i)=maximum(f(i-2)+money of ith house,f(i-1))

This recursive relation ultimately yields to the maximum amount that can be robbed.

We can form our DP matrix and convert the recursive relation in memorization.

### Prerequisite

A 1D array where mone stashed in houses are stored. Let the array to be **money**

### Steps

1. Bases case: IF (n==0) Return 0; IF (n==1) Return money[0]; 2. Initialize DP matrix int house[n]; // DP matrix //initialize all elements with their respective money for(int i=0;i<n;i++) house[i]=money[i]; 3. IF there is only one house, then simply rob the money. house[0]=money[0]; 4. IF there is two house rob from the house having maximum amount house[1]=(money[0]>money[1])?money[0]:money[1]; 5. Formulate the recursive function: for(int i=2;i<n;i++){ //for more houses house[i]=max(house[i]+house[i-2],house[i-1]); } //house[i-2]= f(i-2) // as updated by DP matrix // house[i-2]= f(i-2) // as updated by DP matrix // house[i]( on R.H.S) = money of ith house // as not still updated by DP matrix // house[i] (on L.H.S) = f(i) // as it's going to be updated by DP matrix 6. Return house[n-1]

### Explanation

Let's solve an example using the algorithm: No of houses: 6 Money stashed at houses: 4, 2, 2, 10, 4, 2 Initially DP matrix 4 (0th) | 2 (1st) | 2(2nd) | 10 (3rd) | 4 (4th) | 2 (5th) After step -3 & step - 4: 4 (0th) | 4 (1st) | 2(2nd) | 10 (3rd) | 4 (4th) | 2(5th) At step-5: House index starts from 0Iteration 0:house[2]=max(house[2]+house[0],house[1]); house[2]=6 // house[2]+house[0]=6 &house[1]=4 that means rob at house 0 & then at house 2 4 (0th) | 4 (1st) | 6(2nd) | 10 (3rd) | 4 (4th) | 2 (5th)Iteration 1:house[3]=max(house[3]+house[1],house[2]); house[3]=14 // house[3]+house[1]=14&house[2]=6 that means rob at house 1 & then at house 3 (decision changed) 4 (0th) | 4 (1st) | 6(2nd) | 14 (3rd) | 4 (4th) | 2 (5th)Iteration 2:house[4]=max(house[4]+house[2],house[3]); house[4]=14 // house[4]+house[2]=10&house[3]=14 that means rob at house 1& then at house 3 (no change in last decision) 4 (0th) | 4 (1st) | 6(2nd) | 14 (3rd) | 10 (4th) | 2 (5th)Iteration 3:house[5]=max(house[5]+house[3],house[4]); house[5]=16 // house[5]+house[3]=16&house[4]=10 that means rob at house 1 & then at house 3 & then at house 5(final) 4 (0th) | 4 (1st) | 6(2nd) | 14 (3rd) | 10 (4th) | 16 (5th)

That gives the maximum amount that can be robbed without breaking the security.

## C++ Implementation of House Robber Problem

#include <bits/stdc++.h> using namespace std; int max(int x, int y) { return (x > y) ? x : y; } int rob(vector<int>& money) { int n = money.size(); // base cases if (n == 0) return 0; if (n == 1) return money[0]; int house[n]; // initialize DP matrix for (int i = 0; i < n; i++) house[i] = money[i]; house[0] = money[0]; house[1] = (money[0] > money[1]) ? money[0] : money[1]; // Evaluate the recursive formula for (int i = 2; i < n; i++) { house[i] = max(house[i] + house[i - 2], house[i - 1]); } // return max amount can be robbed return house[n - 1]; } int main() { int n, m; cout << "enter no of houses\n"; cin >> n; vector<int> money; cout << "enter respective money's of houses\n"; for (int i = 0; i < n; i++) { cin >> m; money.push_back(m); } cout << "maximum amount that can be robbed: " << rob(money) << endl; return 0; }

### Output

First run: enter no of houses 4 enter respective money's of houses 1 2 3 1 maximum amount that can be robbed: 4 Second run: enter no of houses 6 enter respective money's of houses 4 2 2 10 4 2 maximum amount that can be robbed: 16

Comments and Discussions!