= Solution
Store `pred[j] = i` whenever a strict improvement sets `D[j] = D[i] + 1`. Initialize predecessors to `NONE`. After the <dynamic programming> pass, return `NONE` if the final position is unreachable; otherwise follow predecessors backwards:
``
route = []
j = n - 1
while j != 0:
route.append(j)
j = pred[j]
route.append(0)
reverse(route)
return route
``
Every stored predecessor is smaller than the current index, so reconstruction terminates. Its stored distance is exactly one smaller, so the output has precisely $D[n-1]$ jumps and each jump satisfies its input bound. Therefore $\boxed{\text{store a minimizing predecessor; reverse the predecessor chain from }n-1\text{ to }0}$. Reconstruction takes $O(n)$ additional <time complexity> and $O(n)$ output space; the total <dynamic programming> bounds remain $\Theta(n^2)$ time and $\Theta(n)$ <space complexity>. Keeping the first predecessor on ties selects one optimal route deterministically.
Back to article page
