Frog Jump
MediumBest of stepping one or two
Problem
A frog on step 0 can jump 1 or 2 steps, each costing the height difference. Return the minimum cost to reach the last stair.
Cost to reach a stone = cheaper of coming from one or two stones back, plus the height gap.
The idea
The cost to reach step i is the cheaper of arriving from i-1 or i-2, each plus the height difference. Only the previous two answers are ever needed, so two rolling variables replace the whole array.
The trick
- dp[i] = min(dp[i-1] + |h[i]-h[i-1]|, dp[i-2] + |h[i]-h[i-2]|).
- O(n) time, O(1) space with two variables.
- Greedy fails — a cheap step now can force an expensive one later.
Step 1 of 7. Brute force: f(5) calls f(4) and f(3) — and each of those splits again. calls 1.
Exponential tree.
1function f(i) {2 if (i === 0) return 0;3 return Math.min(f(i - 1) + a, f(i - 2) + b); // overlapping subproblems4}Input
- nodes
- 1, 0 edges
Memory
- calls
- 1
- f(1) redone
- —
- brute calls
- —
Call stack
- 0visit(f(5))
Output
- with memo
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- heights = [10, 30, 40, 20]
- Output:
- 30
- Explanation:
- 10→30→20 costs 20+10 = 30.
Example 2
- Input:
- heights = [10, 10]
- Output:
- 0
- Explanation:
- One flat jump costs 0.
Example 3
- Input:
- heights = [30, 10, 60, 10, 60, 50]
- Output:
- 40
- Explanation:
- Best route costs 40.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.