Pillar Hops With Reach
Medium1-D Dynamic Programming
Problem
Same pillars as before: heights heights[0..n-1], start on pillar 0, finish on pillar n - 1, and a hop from i to j costs |heights[i] - heights[j]|.
This climber is stronger: from pillar i they may hop to any pillar i + 1, i + 2, …, i + k. Return the minimum total effort.
Example 1
- Input:
- heights = [10, 30, 40, 50, 20], k = 3
- Output:
- 30
0 → 1 → 4: 20 + 10 = 30.
Example 2
- Input:
- heights = [10, 20, 10], k = 1
- Output:
- 20
With reach 1 you must visit every pillar.
Constraints
- 1 ≤ heights.length ≤ 10^4
- 1 ≤ k ≤ 100
- 0 ≤ heights[i] ≤ 10^4
Hint
Show the first hint
The two-hop recurrence had two predecessors. How many does pillar i have now?
Walkthrough
How to approach it
01Clarify before coding
- Can k be larger than n? Yes; then the first pillar can hop anywhere.
- Is the hop cost still the absolute height difference? Yes.
- Why not a sliding-window minimum? Because the cost of the edge depends on both i and j, the window minimum changes for each i; O(n·k) is the intended bound here with k ≤ 100.
02Brute force
Recursively try every hop length from each pillar. Memoising on the pillar index gives the same O(n·k) DP but with recursion depth up to n.
Cost: Without memo: up to kⁿ paths. With memo or table: O(n·k) = 10^6 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.