Frog jump with K distances
MediumBest over the previous k steps
Problem
The frog may jump up to k steps at a time. Return the minimum total cost to reach the last stair.
Same as frog jump, but check all of the last k stones and take the cheapest arrival.
The idea
The same recurrence widened: check every jump of length 1 to k landing on i and take the cheapest. That turns O(n) into O(n·k), which is the price of the extra freedom.
The trick
- Inner loop over the last k positions, guarding the array start.
- O(n·k) time; the rolling-array trick still applies with a window of k.
1
1
·
·
·
·
·
0
1
2
3
4
5
6
n6
Step 1 of 7. dp[i] = number of ways to reach step i. You arrive from one step below or two below. Values: 1, 1, ·, ·, ·, ·, ·. n 6.
1/7
Optimal
timeO(n)spaceO(1)
Two rolling values.
1// dp[i] = ways to reach step i2const dp = [1, 1];3for (let i = 2; i <= n; i++)4 dp[i] = dp[i - 1] + dp[i - 2];5return dp[n];Input
- array
- [1, 1, ·, ·, ·, ·, ·]
Memory
- i
- —
- n
- 6
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- heights = [10, 30, 40, 50, 20], k = 3
- Output:
- 30
- Explanation:
- Jumping up to 3 steps, best cost is 30.
Example 2
- Input:
- heights = [10, 20, 10], k = 2
- Output:
- 0
- Explanation:
- Jump straight over → cost 0.
Example 3
- Input:
- heights = [15, 4, 1, 14, 15], k = 3
- Output:
- 2
- Explanation:
- Best route costs 2.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.