= Solution
<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.
Back to article page
