House Robber

Given an array representing money in each house, return the maximum you can rob without robbing two adjacent houses.

Input:

1,2,3,1

Output:

Reasoning:

We start by initializing two variables to track the maximum amount that can be robbed up to each house: $dp_0 = 1$ (robbing the first house) and $dp_1 = 2$ (robbing the second house, which is more than the first).
At the third house, we have two options: rob the third house ( $3$ ) or rob the first two houses ( $1+2=3$ ), so we choose the maximum of these, which is $3$ , and update $dp_2$ to $3$ since we can't rob the second house if we rob the third.
At the fourth house, we again have two options: rob the first and fourth houses ( $1+1=2$ ) or rob the first and third houses ( $1+3=4$ ), so we choose the maximum of these, which is $4$ .
The final output is the maximum of the last two options, which is $\boxed{4}$ .