467. 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.

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ k ≤ 100` - `0 ≤ h[i] ≤ 1000000000`