mediumDynamic programming, 1D target 25 min
House robber
A thief plans one night on a street of houses in a row. money[i] is the cash in house i. Robbing two houses that stand next to each other sets off an alarm, so the thief never robs two neighbors. Skipping several houses in a row is fine.
Return the most cash the thief can collect.
Example 1
Input
money = [3, 10, 3, 1, 2]Output12Rob houses 1 and 4: 10 + 2 = 12. Robbing every other house gives only 3 + 3 + 2 = 8 or 10 + 1 = 11.
Example 2
Input
money = [5, 1, 1, 5]Output10Rob the first and the last house, skipping the two in the middle.
Example 3
Input
money = [6, 7, 6]Output12Robbing the richest house first takes the 7 and blocks both 6s. The two 6s together are worth more.
Constraints
1 ≤ len(money) ≤ 100
0 ≤ money[i] ≤ 500
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.