= Solution
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 is
$$
\boxed{D[0]=0,\qquad D[j]=1+\min_{\substack{0\le i<j\\i+A[i]\ge j}}D[i]\quad(1\le j<n),}
$$
where 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. Thus
$$
\boxed{\text{time }\Theta(n^2),\qquad\text{auxiliary space }\Theta(n).}
$$
For the source example, the computed <array> is
$$
D=[0,1,1,2,2,2,3,3,3,3,4].
$$
When $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.
Back to article page
