House robber (Memoization)

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

This algorithm uses memoization to improve performance. It's same as the recursive version of House robber, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = {}

def rob(ls):
  if len(ls) <= 0:
    return 0

  if len(ls) not in cache:
    cache[len(ls)] = max(ls[-1] + rob(ls[:-2]), rob(ls[:-1]))

  return cache[len(ls)]

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

print(rob(ls))

const cache = []

function rob(list) {
  if (list.length <= 0) {
    return 0;
  }

  if (cache[list.length] === undefined) {
    cache[list.length] = Math.max(list[list.length - 1] + rob(list.slice(0, -2)), rob(list.slice(0, -1)));
  }
  
  return cache[list.length];
}

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

console.log(rob(list));