Maximize total tips (Memoization)

A restaurant received n orders. The two waiters A and B in the restaurant change different amount of tip, listed in A[] and B[], for an order. Given A can handle max X order and B can handle max Y order, Find out the maximum possible amount of total tips to handle all the orders.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Maximize total tips, 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 = None

def count(a, b, x, y, n):
  if n == 0:
    return 0

  global cache
  if not cache:
    cache = [None] * (n + 1)

  if not cache[n]:
    if x > 0 and y > 0:
      cache[n] = max(a[n-1] + count(a, b, x-1, y, n-1), b[n-1] + count(a, b, x, y-1, n-1))

    cache[n] = b[n-1] + count(a, b, x, y-1, n-1) if (x == 0) else a[n-1] + count(a, b, x-1, y, n-1)

  return cache[n]

N = 5
A = [1, 2, 3, 4, 5]
B = [5, 4, 3, 2, 1]
X = 3
Y = 3

print(count(A, B, X, Y, N))

let cache = null;

function count(a, b, x, y, n) {
  if (n == 0) {
    return 0;
  }

  if (!cache) {
    cache = Array(n + 1);
  }

  if (cache[n] === undefined) {
    if (x > 0 && y > 0) {
      cache[n] = Math.max(a[n-1] + count(a, b, x-1, y, n-1), b[n-1] + count(a, b, x, y-1, n-1));
    }
  
    cache[n] = (x == 0) ? b[n-1] + count(a, b, x, y-1, n-1) : a[n-1] + count(a, b, x-1, y, n-1);
  }

  return cache[n];
}

const N = 5;
const A = [1, 2, 3, 4, 5];
const B = [5, 4, 3, 2, 1];
const X = 3;
const Y = 3;

console.log(count(A, B, X, Y, N));