Cheapest Hops Forward
Stones stand in a line at heights h[0] .. h[n-1]. A frog starts on stone 0 and
must reach stone n-1. From stone i it may hop to any stone i+1 .. i+k that
exists, and a hop from i to j costs |h[i] - h[j]|.
Print the smallest total cost.
h = 10 30 40 50 20, k = 3 -> 30 hop 0 -> 1 -> 4, 20 + 10
h = 10 20 10, k = 2 -> 0 hop 0 -> 2 straight past the 20
Greedily hopping to the nearest stone in height is the tempting wrong answer, and the first sample defeats it: from stone 0 at height 10, stone 1 at height 30 is not the closest reachable height, yet going there is optimal because it sets up a cheap final hop.
The recurrence is direct. The cost to reach j is fixed once the costs to reach every
stone that can hop to j are known, and those are all earlier:
cost[0] = 0
cost[j] = min over i in [j-k, j-1] of cost[i] + |h[i] - h[j]|
Because every dependency has a smaller index, one left-to-right pass fills the table with no recursion.
Two things to get right. The lower bound must be clamped, so the window at small j
starts at 0 rather than at a negative index. And k is an upper limit on the hop, not
the hop size, so every distance from 1 to k must be tried; using only k makes
h = 10 20 10 with k = 2 unreachable from odd positions.
With n = 1 the frog is already home and the answer is 0, which the loop produces on
its own if the table starts at 0 and never runs.
Costs add up: n hops of up to 10^9 each exceeds a 32-bit total.