#82 · Dynamic programming · Intermediate · 70 XP · about 12 min
A robber is planning a night's work along a street of houses, where money[i] is the cash hidden in house i. Houses next door to each other share an alarm, so robbing two adjacent houses brings the police.
Write rob(money) that returns the largest total the robber can take without robbing two houses that stand side by side.
rob([3, 10, 4, 2, 8]) # returns 18 rob([6, 1, 2, 7]) # returns 13 rob([2, 1, 1, 2]) # returns 4
In the last example the best plan robs the first and the last house, skipping two houses in a row.
0 <= len(money) <= 10000 <= money[i] <= 10000First solves only, ranked by stars and then time.