Houses stand in a row, and each one holds some money. You can't rob two houses that are next to each other, because their alarms are connected. Find the most money you can rob.
DSA Animator › DSA Revision › Dynamic Programming › House Robber
Remember: best at i is the larger of skipping house i, or robbing it plus the best at i minus 2. Only the last two answers matter, so two variables are enough. The video solves House Robber (LeetCode 198, Medium) with the 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive House Robber animation.
Houses stand in a row, and each one holds some money. You can't rob two houses that are next to each other, because their alarms are connected. Find the most money you can rob.
For 2, 7, 9, 3 and 1, the best total is 12. Rob the houses with 2, 9 and 1, which are never next to each other.
Trying every set of non-adjacent houses means about 2 to the power n choices. And simply taking every other house isn't reliable, because sometimes the best plan skips two houses in a row.
At each house, you have exactly two choices. Rob it, and add its money to the best total from two houses back. Or skip it, and keep the best total from the house before. The best at each house is the larger of the two, and you only ever need the last two totals.
The best up to house 0 is just 2. At house 1, robbing gives 7 and skipping keeps 2, so the best is 7. At house 2, robbing gives 9 plus 2, which is 11, against 7, so the best is 11. At house 3, robbing gives 3 plus 7, which is 10, but skipping keeps 11, so it stays 11. At house 4, robbing gives 1 plus 11, which is 12, against 11, so the best is 12. The last total is the answer: 12.
In code, keep two numbers: prev 2, the best two houses back, and prev 1, the best one house back. For each house, the best is the larger of prev 1, or prev 2 plus its money. Then shift: prev 1 moves into prev 2, and the new best becomes prev 1. One pass with two variables, so it's O of n time and O of 1 space.
Remember: best at i is the larger of skipping house i, or robbing it plus the best at i minus 2. Only the last two answers matter, so two variables are enough.