2. Find the transition (the formula to compute each state)
Consider house at i. You have two choices:
• If do not rob house i, then the best answer using houses up to i is the same as using houses up to i−1: dp[i]=dp[i−1].
• If do rob house i, then you gain a[i] money, and you are not allowed to take money from house i−1. The best rob from the remaining houses is dp[i−2], so this option gives dp[i]=dp[i−2]+a[i].
So the recurrence is dp[i]=max(dp[i−1], dp[i−2]+a[i]).
This way, calculate all the dp values. The only question left is: what is the final answer? You have established the recurrence. Now let us see the base cases.