Fewest Jumps to the End
Each position holds the maximum number of steps you may jump forward from it,
as in problem 403. Print the FEWEST jumps needed to reach the last position, or
-1 if it cannot be reached. Starting already at the end takes 0 jumps.
The instinct is to jump as far as possible every time. It is wrong, and
2 3 1 1 4 shows why: jumping 2 from the start lands on index 2, whose value
is 1, and the route takes three jumps. Jumping only 1 lands on index 1, whose
value is 3, and reaches the end in two.
Jumping far is not the same as landing well, and no rule that looks at the current position alone can tell the difference.
So it is a shortest-path question on a graph where each position points at everything it can reach. Written as a table:
dp[0] = 0
dp[i + k] = min(dp[i + k], dp[i] + 1) for every k in 1..a[i]
which is O(sum of a) and is what the reference solutions do.
The same collapse as problem 403 gives an O(n) version: sweep once, tracking
the end of the current jump's range and the furthest index reachable from
anywhere inside it, and count a jump each time the sweep passes the range end.