Fewest Pad Jumps

Medium1-D Dynamic Programming

Problem

From stepping pad i you may jump to any pad i + 1 through i + pads[i]. You start on pad 0 and the last pad is guaranteed to be reachable.

Return the minimum number of jumps needed to land on the last pad.

Example 1

Input:
pads = [2, 3, 1, 1, 4]
Output:
2

0 → 1 → 4.

Example 2

Input:
pads = [1, 1, 1, 1]
Output:
3

Constraints

  • 1 ≤ pads.length ≤ 1000
  • 0 ≤ pads[i] ≤ 1000
  • The last pad is reachable from pad 0.

Hint

Show the first hint

Define jumps[i] = fewest jumps from pad i to the end.

Walkthrough

How to approach it

01Clarify before coding

  • Is the end always reachable? Yes, guaranteed.
  • Zero jumps when there is one pad? Yes.
  • Can some intermediate pads be dead ends? Yes, so their cost must be 'infinite', not 0.

02Brute force

Try every route with DFS and keep the shortest.

Cost: Exponential in the number of routes.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.