AI Hints
Home›DSA in Python Tutorial›More Dynamic Programming
DSA in Python · Lesson 95 of 132

Practice: House Robber

No two neighbours.

⏱ 2 min read▶ Video at 1:53:50🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A burglar plans to rob houses along a street, but alarms go off if two neighbouring houses are robbed on the same night. Each house holds a different amount. What's the most the burglar can take? Pause, and think about the last house.

Practice: House Robber
From the video: Practice: House Robber
  • Houses in a row
  • No two neighbours
  • The most money?

Rob it or skip it

At each house, there are 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. We only need to remember two numbers as we walk along. Run it. The best haul is twelve, from houses one, three, and five.

robber.pypython
def rob(houses):
    two_back, one_back = 0, 0
    for money in houses:
        two_back, one_back = one_back, max(one_back, two_back + money)
    return one_back

print(rob([2, 7, 9, 3, 1]))
print(rob([5, 1, 1, 5]))
Output
12
10

Shrinking the table

Often the table only ever looks back one or two steps. Then you don't need the whole table, just a couple of variables. That turns O of N memory into O of one. Climbing stairs and Fibonacci can be shrunk in exactly the same way.

keyvalue
Choicerob, or skip
Robtwo back + money
Skipone back
MemoryO(1) with two variables

Summary

At each house, take the better of robbing it or skipping it. Two variables are enough. Next, measuring how different two words are.

Key takeaways
  • max(skip, rob)
  • Two variables
  • O(n) time, O(1) space
Next up: Practice: Edit Distance — how spell checkers think