LC 403 - Frog Jump
Frog Jump is the problem I recommend to anyone starting dynamic programming. It is small enough to hold in your head, but it walks you through the whole DP ladder: recursion, memoization, tabulation and space optimisation. Once this one clicks, a dozen other problems stop looking scary.
The problem
A frog sits on stair 0 of a staircase with n stairs. Each stair i has a height heights[i]. From stair i the frog can jump to stair i+1 or stair i+2. A jump from stair i to stair j costs |heights[i] - heights[j]| energy. Find the minimum total energy the frog needs to reach stair n-1.
Example: heights = [30, 10, 60, 10, 60, 50]. The answer is 40, using the path 0 โ 2 โ 4 โ 5, which costs 30 + 0 + 10.
Why greedy fails
The tempting move is to always take the cheaper next jump. On the example, greedy jumps 0 โ 1 (cost 20) because it is cheaper than 0 โ 2 (cost 30), and ends up paying more overall. A cheap step now can force expensive steps later. When a local choice changes your future options, think DP, not greedy.
Step 1: Think recursively
Ask the question backwards: how did the frog reach stair i? Only two ways โ from stair i-1 or from stair i-2. So the cheapest way to reach i is the cheaper of those two options.
f(i) = min( f(i-1) + |h[i] - h[i-1]| , f(i-2) + |h[i] - h[i-2]| ), with f(0) = 0, and the second option only valid when i > 1.
This is correct, but every call branches into two more, so the running time is O(2^n). The same subproblems get solved again and again.
Step 2: Memoization (top-down)
Store each f(i) the first time you compute it, in an array dp filled with -1. Before recursing, check whether dp[i] is already known. Now every stair is solved exactly once: O(n) time, O(n) space for the array, plus O(n) recursion stack.
Step 3: Tabulation (bottom-up)
Flip the direction and fill the table from the base case upward. Set dp[0] = 0. For i from 1 to n-1, compute oneStep = dp[i-1] + |h[i] - h[i-1]|, compute twoStep = dp[i-2] + |h[i] - h[i-2]| only when i > 1, and set dp[i] to the smaller one. The answer is dp[n-1].
On the example the table fills as 0, 20, 30, 20, 30, 40. Same O(n) time, but no recursion stack, so no risk of stack overflow on large inputs.
Step 4: Space optimisation
Look at the recurrence again: dp[i] only ever reads dp[i-1] and dp[i-2]. You do not need the whole array, just two variables. Keep prev (the cost to reach i-1) and prev2 (the cost to reach i-2), compute the current value, then shift: prev2 becomes prev, prev becomes current.
Final complexity: O(n) time and O(1) space. This is the answer interviewers are waiting for.
Complexity at a glance
Recursion: O(2^n) time, O(n) stack. Memoization: O(n) time, O(n) space plus O(n) stack. Tabulation: O(n) time, O(n) space. Space optimised: O(n) time, O(1) space.
Follow-up: k jumps
A common follow-up lets the frog jump up to k stairs. The recurrence becomes the minimum over j from 1 to k of dp[i-j] + |h[i] - h[i-j]|. That is O(nยทk) time and O(n) space. Notice the two-variable trick no longer works directly, because you now need the last k values, not just the last two.
How to talk about it in an interview
Start with the recursion and say out loud why greedy fails. Point out the overlapping subproblems, then memoize. Convert to tabulation, then notice the dependency is only on the last two states and drop to O(1) space. That progression shows the interviewer you understand DP as a method, not a memorised template โ which is exactly what they are testing.
The pattern to remember
Whenever the answer at step i depends only on a fixed number of earlier steps, you can move from recursion to a table to a handful of variables. Frog Jump is the cleanest example of that ladder. Climbing Stairs, House Robber and Min Cost Climbing Stairs all follow the same shape.
// Memoization
function frogJump(h) {
const dp = new Array(h.length).fill(-1);
const f = (i) => {
if (i === 0) return 0;
if (dp[i] !== -1) return dp[i];
let best = f(i - 1) + Math.abs(h[i] - h[i - 1]);
if (i > 1) best = Math.min(best, f(i - 2) + Math.abs(h[i] - h[i - 2]));
return (dp[i] = best);
};
return f(h.length - 1);
}
// Space optimised โ O(n) time, O(1) space
function frogJumpOptimal(h) {
let prev = 0, prev2 = 0;
for (let i = 1; i < h.length; i++) {
const one = prev + Math.abs(h[i] - h[i - 1]);
const two = i > 1 ? prev2 + Math.abs(h[i] - h[i - 2]) : Infinity;
const cur = Math.min(one, two);
prev2 = prev;
prev = cur;
}
return prev;
}
frogJumpOptimal([30, 10, 60, 10, 60, 50]); // 40
