Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / e / 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.