Find the transition (the formula to compute each state)
Consider house at . You have two choices:
• If do not rob house , then the best answer using houses up to is the same as using houses up to :
• If do rob house , then you gain money, and you are not allowed to take money from house . The best rob from the remaining houses is , so this option gives
So the recurrence is
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.