= Minimum forward-jump dynamic programming
{title2=$D[j]=1+\min\{D[i]:0\le i<j,\ i+A[i]\ge j\}$}
For nonnegative maximum jump lengths in an <array>, let $D[0]=0$ and let unreachable positions have value $\infty$. Classifying a route to $j$ by its penultimate position proves this <dynamic programming recurrence>. Increasing $j$ is a valid dependency order because every jump advances. Scanning all previous positions uses $\Theta(n^2)$ <time complexity> and $\Theta(n)$ <space complexity>. Store a minimizing predecessor to reconstruct a shortest route.
Back to article page
