House Robber

Maximize loot from a row of houses without robbing two adjacent ones. At each house choose the better of skipping it or robbing it plus the best from two houses back.

Category: Dynamic Programming
Time complexity: O(n)
Space complexity: O(n)

Pseudocode

dp[i] = max(
  dp[i−1],            (skip)
  a[i] + dp[i−2])     (rob)

Reference implementation

for i in range(n):
    rob = a[i] + (dp[i-2] if i&gt;=2 else 0)
    skip = dp[i-1] if i&gt;=1 else 0
    dp[i] = max(rob, skip)

Open the interactive House Robber visualisation →