Maximize total tips (Tabulation)

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

Building upon understanding of Maximize total tips (Memoization). Pay attention to the cache. 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
• Javascript
•  Run

def count(a, b, x, y, n):
  cache = [0] * n

  for i in range(n):
    if x > 0 and y > 0:
      cache[i] += cache[i - 1] if i > 0 else 0 
      if (a[i] > b[i]):
        cache[i] += a[i]
        x -= 1
      else:
        cache[i] += b[i]
        y -= 1
    elif x > 0:
      cache[i] += cache[i - 1] + a[i]
      x -= 1
    else:
      cache[i] += cache[i - 1] + b[i]
      y -= 1
  
  return cache[n - 1]
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))

function count(a, b, x, y, n) {
  const cache = Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    if (x > 0 && y > 0) {
      cache[i] +=  (i > 0) ? cache[i - 1] : 0;
      if (a[i] > b[i]) {
        cache[i] += a[i];
        x--;
      } else {
        cache[i] += b[i];
        y--;
      }
    } else if (x > 0) {
      cache[i] += cache[i - 1] + a[i];
      x--;
    } else {
      cache[i] += cache[i - 1] + b[i];
      y--;
    }
  }
  
  return cache[n - 1];
}

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));