Frog Jump

Easy15–20 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftAdobe

A frog starts on the first stair of a staircase, given as an array of stair heights, and wants to reach the last one. From any stair, it can jump to the very next stair or hop over one to land two stairs ahead — and every jump costs the absolute difference in height between the stair it leaves and the stair it lands on. Find the minimum total cost of any path from the first stair to the last. Reaching a stair is always the result of one of exactly two moves: a one-step jump from the stair right before it, or a two-step jump from the stair two before it. That makes the cheapest way to reach any stair depend only on the cheapest way to reach one of those two closer stairs, plus the height difference of whichever jump was taken. Starting from stair 0 — free, since the frog begins there — and building that answer stair by stair means every later stair's cheapest cost only ever depends on costs that have already been worked out.

Test Case 1:

Input:heights = [10, 20, 30, 10]

Output:20

Explanation:The cheapest path is 0→1→3: |20-10|+|10-20| = 10+10 = 20, mixing a one-step jump with a two-step jump.

Test Case 2:

Input:heights = [40, 20, 70, 20, 70, 60]

Output:40

Explanation:The cheapest path is 0→2→4→5: |70-40|+|70-70|+|60-70| = 30+0+10 = 40, all two-step jumps except the last.

Test Case 3:

Input:heights = [10, 10]

Output:0

Explanation:Both stairs are the same height, so the single jump between them costs 0.

Constraints

◆1 ≤ heights.length ≤ 30
◆0 ≤ heights[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Work backward from the last stair: the cheapest way to reach stair i is whichever is smaller — the cheapest way to reach stair i-1 plus the cost of a one-step jump from there, or the cheapest way to reach stair i-2 plus the cost of a two-step jump from there (when i-2 is a valid stair at all). Stair 0 costs nothing to "reach" since the frog starts there. Asking this question starting from the very last stair and letting it recurse down to stair 0 answers the whole problem, but the same stair's cheapest cost gets recomputed every time a different later stair happens to ask for it again.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] h;

    public int frogJump(int[] heights) {
        this.h = heights;
        return solve(heights.length - 1);
    }

    private int solve(int i) {
        if (i == 0) return 0;
        int oneStep = solve(i - 1) + Math.abs(h[i] - h[i - 1]);
        if (i == 1) return oneStep;
        int twoStep = solve(i - 2) + Math.abs(h[i] - h[i - 2]);
        return Math.min(oneStep, twoStep);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Let dp[i] hold the cheapest total cost to reach stair i from stair 0. dp[0] is 0 (the frog starts there for free), and dp[1] can only be reached by a one-step jump from stair 0. From stair 2 onward, dp[i] is the smaller of two options computed from already-filled entries: dp[i-1] plus a one-step jump, or dp[i-2] plus a two-step jump. Filling the table from the bottom up means every option is always based on costs that were already finalized earlier in the pass, and the answer is simply whatever ends up in the last slot.

TimeO(n)