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 / c

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.