Given an array representing money in each house, return the maximum you can rob without robbing two adjacent houses.
Example:
Input:
1,2,3,1
Output:
4
Reasoning:
We start by initializing two variables to track the maximum amount that can be robbed up to each house: dp0=1 (robbing the first house) and dp1=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 dp2 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 4.