Frog Jump with K Steps
MediumP3Coding
There are N buildings in a row with heights h[0..N-1]. Spider-Man starts on the first building. From building i he can jump to any building i + 1, i + 2, ..., i + k (as long as it exists), paying |h[i] - h[j]| for landing on building j.
Return the minimum total cost to reach the last building. With one building the cost is 0.
Example 1
- Input
- h = [10,30,40,20], k = 2
- Output
- 30
- Why
- Jump 0 to 1 (20), then 1 to 3 (10): total 30. Jumping 0 to 2 (30) and then to 3 (20) costs 50.
Example 2
- Input
- h = [10,20,10], k = 1
- Output
- 20
Example 3
- Input
- h = [5], k = 3
- Output
- 0
Constraints
- 1 <= N <= 10^4
- 1 <= k <= 100
- 1 <= h[i] <= 10^4
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.