Give a special keyboard with the following four keys Key 1: Prints 'A' on screen, Key 2: Select screen, Key 3: Copy selection, Key 4: Paste selection on screen after what has already been printed. Given a number N times (with the above four keys), write a program to produce maximum numbers of A's.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Print maximum number of A’s using given four keys, 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:

# Python implementation

cache = None

def count(n):
  if n < 7:
    return n
  
  global cache
  if not cache:
    cache = [None] * (n + 1)

  if not cache[n]:
    mx = 0

    for i in range(n - 3, -1, -1):
      mx = max(mx, (n - i - 1) * count(i))

    cache[n] = mx

  return cache[n]

n = 7

print(count(n))

// Javascript implementation

let cache = null;

function count(n) {
  if (n < 7) {
    return n;
  }

  if (!cache) {
    cache = [];
  }

  if (cache[n] === undefined) {
    let max = 0;

    for (let i = n - 3; i >= 0; i--) {
      max = Math.max(max, (n - i - 1) * count(i));
    }

    cache[n] = max;
  }

  return cache[n];
}

const n = 7;

console.log(count(n));

Print maximum number of A’s using given four keys (Memoization)

Hint