# House Robber  Difficulty Level Medium
Depth First Search

The House Robber Problem states that, in a neighborhood in a city, there is a single row of n houses. A thief is planning to carry a heist in this neighborhood. He knows how much gold is concealed in each of the houses.

However, in order to avoid triggering an alarm and raise suspicion, he plans to carry heist in such a way that no two consecutive houses are looted. i.e. if the house at index = i is looted, the houses at i-1 and i+1 are not looted.

Find out what is the maximum number of gold the thief can steal following the given constraints.

## Example  ```Input 1: arr[] = [2,3,4,2,3]
Maximum gold = [2, X, 4, X, 3] = 9
Output: 6

Input 2: arr[] = [3,8,10,4,2,3]
Maximum gold = [3, X, 10, X, X, 3] = 16
Output: 15

Input 2: arr[] = [3,8,10,4,2,3,11]
Maximum gold = [3, X, 10, X, 2, X, 11] = 26
Output: 26```

Explanation: in example 2, the thief has to get to 1st, 3rd, and 6th house to collect the maximum number of gold given the constraints.

Types of Solution

1. Recursive
2. Dynamic Programming :
• Memoized Solution
• Tabulated Solution
• Space Optimized DP solution
Distinct Subsequences

## Recursive solution for House Robber  Given an array, the solution is to find the maximum sum subsequence where no two selected elements are adjacent. we implement this in the following way:

1. Start traversing arr[] from right to left.
2. If an element arr[i] is selected then the next element (arr[i-1]) cannot be selected.
3. If an element(arr[i]) is not selected then the next element arr[i-1] can be selected.
4. Perform steps 2 and 3 recursively and return the maximum of values obtained in steps 2 and 3.

### C++ Program

```#include <iostream>
using namespace std;

int maxGold (int gold[],int n)
{
if(n <= 0)
return 0;

// select the current element
int select = gold[n-1] + maxGold(gold,n-2);
// not selecting the current element
int notselect = maxGold(gold,n-1);

// return maximum of both of above
return max(select,notselect);
}

int main()
{
int gold[] = {3,8,10,4,2,3};
int n = sizeof(gold)/sizeof(int);

cout<<"Maximum gold looted = "<<maxGold(gold,n);
return 0;
}```
`Maximum gold looted = 16`

### Java Program

```import java.io.*;

class tutorialcup
{
static int maxGold (int gold[],int n)
{
if(n <= 0)
return 0;

// select the current element
int select = gold[n-1] + maxGold(gold,n-2);
// not selecting the current element
int notselect = maxGold(gold,n-1);

// return maximum of both of above
return Math.max(select,notselect);
}

public static void main (String[] args)
{
int gold[] = {3,8,10,4,2,3};
int n = gold.length;

System.out.print("Maximum gold looted = "+maxGold(gold,n));
}
}```
`Maximum gold looted = 16`

### Complexity Analysis

1. Time complexity T(n) = O(2n), recursive calls.
2. Space complexity A(n) = O(1)

## Dynamic Programming  The major drawback of the recursive solution is its exponential time complexity. This Happens as the recursive solution tries to solve certain subproblems repeatedly. This increases the time taken by the algorithm. The exponential time complexity of the recursive solution can be reduced to linear time complexity using dynamic programming. This method utilizes extra space to store solutions of the subproblems, later in the program if that subproblem is called again, it’s stored value can be directly used instead of recalculating it. This reduces the complexity from exponential to linear order.

Count ways to reach the nth stair using step 1, 2 or 3

We will implement Dynamic Programming Solution in the following ways :

### Memoized Solution for House Robber

here we create a map memo and store subproblems as it’s keys and solutions to the subproblems as values of the map. The implementation code is similar to the recursive approach, except for slight changes and usage of Map.

The memo map is given below: #### C++ Program

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxGold (int gold[],int n, unordered_map <int,int> &memo)
{
int key = n;

// if solution for subproblem maxGold(gold,n,memo)
// has not been calculated
// calulate it
if(memo.find(key) == memo.end())
{
if(n <= 0)
{
memo[key] = 0;
return memo[key];
}

// select the current element
int select = gold[n-1] + maxGold(gold,n-2,memo);
// not selecting the current element
int notselect = maxGold(gold,n-1,memo);

// return maximum of both of above
memo[key] = max(select,notselect);
}

// return value of subproblem after being calculated
return memo[key];
}

// main function to implement above function
int main()
{
int gold[] = {3,8,10,4,2,3};
int n = sizeof(gold)/sizeof(int);

// map to store mapping between particular subproblem and it's value
unordered_map <int,int> memo;
cout<<"Maximum gold looted = "<<maxGold(gold,n,memo);
return 0;
}```
`Maximum gold looted = 16`

#### Java Program

```import java.io.*;
import java.util.*;
class tutorialcup
{
static int maxGold (int gold[],int n, HashMap <Integer,Integer> memo)
{
int key = n;

// if solution for subproblem maxGold(gold,n,memo)
// has not been calculated
// calulate it
if(!memo.containsKey(key))
{
if(n <= 0)
{
memo.put(key,0);
return memo.get(key);
}

// select the current element
int select = gold[n-1] + maxGold(gold,n-2,memo);
// not selecting the current element
int notselect = maxGold(gold,n-1,memo);

// return maximum of both of above
memo.put(key, Math.max(select,notselect));
}

// return value of subproblem after being calculated
return memo.get(key);
}

public static void main (String[] args)
{
int gold[] = {3,8,10,4,2,3};
int n = gold.length;

HashMap <Integer,Integer> memo = new HashMap <Integer,Integer>();
System.out.print("Maximum gold looted = "+maxGold(gold,n,memo));
}
}```
`Maximum gold looted = 16`

#### Complexity Analysis

1. Time Complexity : T(n) = O(n), single array traversal.
2. Space Complexity : A(n) = O(n), extra space for map.
Largest divisible pairs subset

### Tabulated Solution for House Robber

we create a table (linear array) where the subproblems are the array index and solutions to the subproblems are the value at that particular index.

#### Algorithm

1. Create an array table[] to store the sub-problems
2. Define some base cases (for n = 0,1,2).
3. return 0 for n = 0.
4. Update table = gold and table = max(gold, gold).
5. Traverse the array from i = 2 to the end of the array.
6. For every index, update table[i] = max(table[i-2] + gold[i] , table[i-1]), this step defines the two cases, if an element is selected then the previous element cannot be selected and if an element is not selected then the previous element can be selected.
7. return the value table[n-1].

We display the above process below: #### C++ Program

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxGold (int gold[],int n1)
{
// base cases
if (n1 == 0)
return 0;
if (n1 == 1)
return gold;
if (n1 == 2)
return max(gold, gold);

// table[i] represent the maximum value stolen
// so far after reaching house i.
int table[n1];

// Initialize the table and table
table = gold;
table = max(gold, gold);

// Fill remaining positions
for (int i = 2; i<n1; i++)
table[i] = max(gold[i]+table[i-2], table[i-1]);

return table[n1-1];
}

// main function to implement above function
int main()
{
int gold[] = {3,8,10,4,2,3};
int n = sizeof(gold)/sizeof(int);

cout<<"Maximum gold looted = "<<maxGold(gold,n);
return 0;
}```
`Maximum gold looted = 16`

#### Java Program

```import java.io.*;
import java.util.*;
class tutorialcup
{
static int maxGold (int gold[],int n)
{
// base cases
if (n == 0)
return 0;
if (n == 1)
return gold;
if (n == 2)
return Math.max(gold, gold);

// table[i] represent the maximum value stolen
// so far after reaching house i.
int table[] = new int[n];

// Initialize the table and table
table = gold;
table = Math.max(gold, gold);

// Fill remaining positions
for (int i = 2; i<n; i++)
table[i] = Math.max(gold[i]+table[i-2], table[i-1]);

return table[n-1];
}

public static void main (String[] args)
{
int gold[] = {3,8,10,4,2,3};
int n = gold.length;

System.out.print("Maximum gold looted = "+maxGold(gold,n));
}
}```
`Maximum gold looted = 16`

#### Complexity Analysis

1. Time Complexity : T(n) = O(n), single traversal.
2. Space Complexity : A(n) = O(n), for table[].
Find the node with minimum value in a Binary Search Tree

### Space Optimized DP solution for House Robber

By carefully observing the tabulated DP solution, we deduce that only the last two indices (i-1 and i-2) are required to calculate the solution of the i-th subproblem. i.e. we need only table[i-2] and table[i-1] to calculate the value of table[i]. So, we eliminate the table[] array and replace it with two auxiliary variables.

#### Algorithm

1. Define some base cases (for n = 0,1,2).
2. return 0 for n = 0.
3. Create two variables val1 and val2.
4. assign val1 = gold , value2 = max(gold, gold).
5. define a variable maxLoot to store the answer.
6. Traverse the array from the second element to the end of the array.
7. For every index = i, update maxLoot  = max(val1 + gold[i],val2), this step defines the two cases, if an element is selected then the previous element cannot be selected and if an element is not selected then the previous element can be selected.
8. Also, For every index, Update val1= val2 and val2 = maxLoot.
9. return the final value of maxLoot, after the array traversal.

#### C++ Program

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxGold (int gold[],int n)
{
// base cases
if (n == 0)
return 0;
if (n == 1)
return gold;
if (n == 2)
return max(gold, gold);

// define and initialize val1 and val2
int val1 = gold;
int val2 = max(gold, gold);
// define maxLoot to obtain maximum value of gold stolen
int maxLoot;

// traverse to find the final value of maxLoot
for (int i = 2; i<n; i++)
{
maxLoot = max(gold[i]+val1, val2);
val1 = val2;
val2 = maxLoot;
}

return maxLoot;
}

// main function to implement above function
int main()
{
int gold[] = {3,8,10,4,2,3};
int n = sizeof(gold)/sizeof(int);

cout<<"Maximum gold looted = "<<maxGold(gold,n);
return 0;
}```
`Maximum gold looted = 16`

#### Java Program

```import java.io.*;
import java.util.*;
class tutorialcup
{
static int maxGold (int gold[],int n)
{
// base cases
if (n == 0)
return 0;
if (n == 1)
return gold;
if (n == 2)
return Math.max(gold, gold);

// define and initialize val1 and val2
int val1 = gold;
int val2 = Math.max(gold, gold);
int maxLoot = 0;

// traverse to find the final value of maxLoot
for (int i = 2; i<n; i++)
{
maxLoot = Math.max(gold[i]+val1, val2);
val1 = val2;
val2 = maxLoot;
}

return maxLoot;
}

public static void main (String[] args)
{
int gold[] = {3,8,10,4,2,3};
int n = gold.length;

System.out.print("Maximum gold looted = "+maxGold(gold,n));
}
}```
`Maximum gold looted = 16`

#### Complexity Analysis

1. Time Complexity : T(n) = O(n), single traversal.
2. Space Complexity : A(n) = O(1), used only two extra variables .