Imagine you're hopping along a number line. Each number on the line represents a position in a list of numbers. Each number on the line tells you the maximum distance you can hop forward from that position. Find the fewest hops needed to reach the very end of the number line, starting from the beginning. If a number is zero, you can't hop from that position at all.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find minimum of jumps to reach end, 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 = {}

def jump(n):
  if len(n) <= 1:
    return 0

  if len(n) not in cache:
    mn = float('inf')
    
    for i in range(1, n[0] + 1):
      mn = min(mn, 1 + jump(n[i:]))
    
    cache[len(n)] = mn

  return cache[len(n)]

ls = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]

print(jump(ls))

// Javascript implementation

const cache = [];

function jump(n) {
  if (n.length <= 1) {
    return 0;
  }

  if (cache[n.length] === undefined) {
    let min = Infinity;
    
    for (let i = 1; i <= n[0]; i++) {
      min = Math.min(min, 1 + jump(n.slice(i)));
    }

    cache[n.length] = min;
  }

  return cache[n.length];
}

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

console.log(jump(list));

Find minimum of jumps to reach end (Memoization)

Hint