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)^th house or he can rob from i^th house after robbing from (i-2)^th house. To maximize the money simply find which results in maximum amount. In terms of recursive relation we can write,

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 0

Iteration 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