Standard Bar Dynamic Programming · 1D DP O(n*k) · O(n)
A rescue scout traverses n ridge markers and may leap over up to k markers in a single bound. Crossing from marker i to marker j burns stamina equal to the absolute elevation difference between them. The expedition lead needs the least-strenuous itinerary across the ridge, so the scout's wrist computer must report the minimum stamina for the full traverse.
Input: Integers n and k, plus an array height of n integers giving each marker's elevation.
Output: Return the minimum total stamina to travel from marker 0 to marker n-1 with jumps of at most k.
1 <= n <= 10^51 <= k <= 1000 <= height[i] <= 10^4Input: {"n":4,"k":2,"height":[10,40,30,10]}
Output: 40
0 to 2 costs |10-30| = 20, then 2 to 3 costs |30-10| = 20 — total 40.
Input: {"n":5,"k":3,"height":[10,40,50,20,60]}
Output: 50
Hop 0 to 3 directly (|10-20| = 10), then 3 to 4 (|60-20| = 40) — total 50; every other route lands at 50 or worse.