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

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 implementation

def jump(n):
  cache = [float('inf') for _ in range(len(n))]
  cache[len(n) - 1] = 0

  for i in range(len(n) - 2, -1, -1):
    mn = float('inf')

    for j in range(i + 1, min(i + n[i] + 1, len(n))):
      mn = min(mn, 1 + cache[j])

    cache[i] = mn

  return cache[0]

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

print(jump(ls))

// Javascript implementation

function jump(n) {
  const cache = Array(n.length).fill(Infinity);
  cache[n.length - 1] = 0;

  for (let i = n.length - 2; i >= 0 ; i--) {
    let min = Infinity;

    for (let j = i + 1; j < Math.min(i + n[i] + 1, n.length); j++) {
      min = Math.min(min, 1 + cache[j]);
    }

    cache[i] = min;
  }

  return cache[0];
}

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

console.log(jump(list));

Find minimum of jumps to reach end (Tabulation)

Hint