A robber wants to steal money from n houses built in a line, each of which contains some money in it. Given he can’t steal from two adjacent houses, find the maximum amount of money can be steal.

Hint

Building upon understanding of House robber (Memoization). Tabulation essentially reconstructs the cache.

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def rob(ls):
  cache = {}

  cache[0] = 0
  cache[1] = ls[0]

  for i in range(2, len(ls) + 1):
    cache[i] = max(ls[i - 1] + cache[i - 2], cache[i - 1])

  return cache[len(ls)]

ls = [6, 7, 1, 3, 8, 2, 4]

print(rob(ls))

// Javascript implementation

function rob(list) {
  const cache = [];

  cache[0] = 0;
  cache[1] = list[0];

  for (let i = 2; i < list.length + 1; i++) {
    cache[i] = Math.max(list[i - 1] + cache[i - 2], cache[i - 1]);
  }

  return cache[list.length];
}

const list = [6, 7, 1, 3, 8, 2, 4];

console.log(rob(list));

House robber (Tabulation)

Hint