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 ith house or not.

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

Now, in case of taking decision whether to rob from ith 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 ith 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.

Pre-requisite:

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]

Example with 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:

#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