Frog Jump with K Distances

Medium15–20 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftAdobe

This is the same frog and staircase as before, except the frog is no longer limited to jumping 1 or 2 stairs at a time — from any stair it can jump ahead by any distance from 1 up to a given k. Every jump still costs the absolute difference in height between the stair it leaves and the stair it lands on, and the goal is still the minimum total cost of any path from the first stair to the last. The same idea scales up directly: the cheapest way to reach a stair depends only on the cheapest way to reach one of the (up to) k stairs behind it, plus the cost of whichever jump was used to get there. Instead of comparing just two options — a one-step jump and a two-step jump — every stair now compares up to k options, one for each possible jump distance, and keeps the cheapest. Filling this in from the first stair onward, so every option always points back to an already-solved smaller stair, turns what would otherwise be an exponential search into a single pass.

Test Case 1:

Input:heights = [20, 40, 50, 60, 30], k = 3

Output:30

Explanation:The cheapest route is 0→1→4: |40-20|+|30-40| = 20+10 = 30, a one-step jump followed by a full 3-step jump.

Test Case 2:

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

Output:20

Explanation:The cheapest route is 0→1→3: |20-10|+|10-20| = 10+10 = 20, a one-step jump followed by a two-step jump.

Test Case 3:

Input:heights = [7, 4, 4, 2, 6, 6, 3], k = 4

Output:4

Explanation:The cheapest route is 0→4→5→6: |6-7|+|6-6|+|3-6| = 1+0+3 = 4, mixing a 4-step jump with two smaller ones.

Constraints

◆1 ≤ heights.length ≤ 30
◆1 ≤ k ≤ heights.length
◆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

This generalizes the two-jump version of the problem: instead of only being able to jump 1 or 2 stairs ahead, the frog can jump anywhere from 1 up to k stairs ahead in a single move. The cheapest way to reach stair i is still built from smaller sub-problems — just more of them now: for every valid jump distance j from 1 to k, the cheapest way to reach stair i-j plus the cost of that j-size jump is a candidate, and the smallest candidate across all valid j wins. Recursing from the last stair down to stair 0 explores every candidate, but without caching, the cheapest cost for a given stair gets recomputed every time a different later stair asks for it.

TimeO(k^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] h;
    private int k;

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

    private int solve(int i) {
        if (i == 0) return 0;
        int best = Integer.MAX_VALUE;
        for (int j = 1; j <= k && i - j >= 0; j++) {
            int cost = solve(i - j) + Math.abs(h[i] - h[i - j]);
            best = Math.min(best, cost);
        }
        return best;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Fill dp[i] — the cheapest cost to reach stair i — from the bottom up instead of recursing from the top down. dp[0] is 0, since the frog starts there. For every later stair i, checking every valid jump distance j from 1 to k and taking dp[i-j] plus that jump's cost gives a set of candidates, and dp[i] becomes whichever candidate is smallest. Because i is processed only after every stair it could possibly jump from has already been filled in, each candidate is always looked up rather than recomputed, and the final answer is just whatever ends up in the last slot.

TimeO(n·k)