Editor

House Robber

#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.

Examples

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.

Constraints

  • 0 <= len(money) <= 1000
  • 0 <= money[i] <= 10000

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.