SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Beginner

House Robber Visualizer

best[i] is the most money from the first i houses. Either skip house i (keep best[i − 1]) or rob it and add it to best[i − 2]. Take the bigger one.

Start the House Robber simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. best[0] = 0: with no houses there is nothing to take.
  2. best[1] = 2: with one house, rob it.
  3. House 2 has 7. Skip it: 2. Rob it: best[0] + 7 = 7.
  4. Robbing wins: best[2] = 7.
  5. House 3 has 9. Skip it: 7. Rob it: best[1] + 9 = 11.
  6. Robbing wins: best[3] = 11.
  7. House 4 has 3. Skip it: 11. Rob it: best[2] + 3 = 10.
  8. Skipping wins: best[4] = 11.
  9. House 5 has 1. Skip it: 11. Rob it: best[3] + 1 = 12.
  10. Robbing wins: best[5] = 12.
  11. The most you can take is 12. Highlighted houses are one way to get it.

Try it with your own input →

1D DP: house robber in Java, Python, C++, C and JavaScript

int rob(int[] houses) {
  int n = houses.length;
  int[] best = new int[n + 1];
  best[1] = houses[0];
  for (int i = 2; i <= n; i++) {
    best[i] = Math.max(best[i - 1], best[i - 2] + houses[i - 1]);
  }
  return best[n];
}
def rob(houses):
    n = len(houses)
    best = [0] * (n + 1)
    best[1] = houses[0]
    for i in range(2, n + 1):
        best[i] = max(best[i - 1], best[i - 2] + houses[i - 1])
    return best[n]
int rob(const vector<int>& houses) {
  int n = houses.size();
  vector<int> best(n + 1, 0);
  best[1] = houses[0];
  for (int i = 2; i <= n; i++) {
    best[i] = max(best[i - 1], best[i - 2] + houses[i - 1]);
  }
  return best[n];
}
int rob(int houses[], int n) {
  int best[n + 1];
  best[0] = 0;
  best[1] = houses[0];
  for (int i = 2; i <= n; i++) {
    int take = best[i - 2] + houses[i - 1];
    best[i] = best[i - 1] > take ? best[i - 1] : take;
  }
  return best[n];
}
function rob(houses) {
  const n = houses.length;
  const best = new Array(n + 1).fill(0);
  best[1] = houses[0];
  for (let i = 2; i <= n; i++) {
    best[i] = Math.max(best[i - 1], best[i - 2] + houses[i - 1]);
  }
  return best[n];
}

In an interview

LeetCode 198, House Robber: never rob two neighbours. Follow-ups: 213 (houses in a circle) and 337 (houses on a tree).

Only the last two values are read, so two variables replace the array. The circular version runs this twice: once without the first house, once without the last.

More dynamic programming