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

Describe routes by array indices, so repeated entry values cannot confuse positions. Two valid routes areThe first uses jump lengths $2,2,5,1$, bounded respectively by $A[0]=2$, $A[2]=3$, $A[4]=5$, $A[9]=7$. The second uses lengths $2,1,1,4,2$, bounded by $2,3,3,5,2$ at its departing positions. Both reach the final index without landing at the zero entry at index six.

After one jump, the largest reachable index is two. After at most two jumps, the reachable indices form the prefix $[0,5]$: index two can reach five, but no reachable departure before that second jump can go further. From indices zero through five, the largest endpoint of one further jump is $4+A[4]=9$. Thus three jumps cannot reach index ten.

The two routesare valid and use four jumps. Therefore $\boxed{\text{the minimum is four jumps, and the minimizing route is not unique}}$. The frontier argument proves the lower bound independently of merely exhibiting a route. In fact these are the two minimizing index sequences: the last departure in a four-jump solution must be eight or nine, reached in three jumps through four, which is reached in two jumps only through two.

Dynamic programming solves related subproblems once, stores their results, and combines those results in an order consistent with their dependencies. The state must retain all information that determines the remaining choices and their costs. Here an adequate dynamic programming state is the current array index, since future jumps depend only on that index and the fixed input.

The principle of optimality says that the remaining part of an optimal solution must be optimal for the residual problem defined by its state. Equivalently here, the prefix ending at a particular intermediate position of a shortest route must be a shortest route to that position: replacing it by a shorter prefix would shorten the entire route. This is the optimal substructure needed by the dynamic programming recurrence.

Thus $\boxed{\text{store an optimum for each state; combine previously solved states by an optimality recurrence}}$. Overlapping routes share states, so storing results avoids repeatedly solving the same subproblem.

Let $D[j]$ be the minimum number of jumps from index zero to index $j$, with $\infty$ denoting an unreachable position. The minimum forward-jump dynamic programming recurrence iswhere the minimum of an empty set is $\infty$ and $1+\infty =\infty$. Compute it in increasing index order:

D[0] = 0
for j = 1, ..., n-1:
    D[j] = INFINITY
    for i = 0, ..., j-1:
        if D[i] != INFINITY and A[i] >= j-i:
            D[j] = min(D[j], D[i] + 1)
return D[n-1]

For algorithm correctness, classify any route to $j>0$ by its penultimate index $i$. Every jump advances, so $i<j$, and legality requires $A[i]\ge j-i$. By the principle of optimality, a shortest prefix to $i$ can be used; this gives the lower bound represented by the recurrence. Conversely, a minimizing reachable predecessor supplies an actual route of length $D[i]+1$, proving attainability. Mathematical induction on $j$ therefore proves every stored value correct.

There are $n(n-1)/2$ predecessor tests, and two arrays are unnecessary when only the number is required. ThusFor the source example, the computed array isWhen $n=1$, zero jumps are needed even if the lone entry is zero. An unreachable final position returns $\infty$. Testing A[i] >= j-i also avoids forming a potentially overflowing sum i + A[i] in bounded implementations. A faster frontier-based algorithm is possible, but the displayed method directly supplies the requested dynamic programming 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.