☕ DSA Java Articles

Topics › Dynamic Programming › 1D DP

Frog jump with K distances

Medium TUF ID 289 A2Z

Java source ↗ Edit this article ↗

Problem

There are n stairs with heights h[0..n-1]. A frog starts on stair 0 and wants to reach stair n - 1. From stair i it may jump to any of the stairs i + 1, i + 2, ..., i + k. A jump from stair i to stair j costs |h[i] - h[j]| energy. Return the minimum total energy to reach the last stair. (GeeksforGeeks calls this problem “Minimal Cost”.)

Typical constraints: n up to about 10^5, 1 ≤ k ≤ 100, heights up to 10^4. With k = 2 this is exactly the plain Frog Jump.

Example 1

h = [10, 30, 40, 50, 20], k = 3
answer = 30         // 0 -> 1 costs 20, then 1 -> 4 (a jump of 3) costs |30 - 20| = 10

Example 2

h = [10, 20, 10], k = 1
answer = 20         // k = 1 forces 0 -> 1 -> 2: 10 + 10

Approach 1: Recursion

Intuition. Generalise the Frog Jump argument. Let f(i) be the minimum energy to reach stair i. The last jump into stair i had some length j between 1 and k, so it came from stair i - j (which must exist, so i - j ≥ 0). The cost after that jump does not depend on how the frog reached i - j, so the route to i - j should be the cheapest one, f(i - j). Try every j and keep the best:

f(0) = 0
f(i) = min over j = 1..k with i - j ≥ 0 of  f(i - j) + |h[i] - h[i - j]|

The two hand-written options of Frog Jump simply become a loop.

Algorithm.

  1. If i == 0, return 0.
  2. For each j from 1 to k while i - j ≥ 0, compute f(i - j) + |h[i] - h[i - j]|.
  3. Return the minimum of those values.
static int recursive(int[] h, int k) {
    return solve(h.length - 1, h, k);
}

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

Complexity. Time up to O(k^n): each call can branch k ways, and the same stairs are solved repeatedly. Space O(n) for the recursion depth.

Approach 2: Memoization

Intuition. The state is still just the stair index, so there are only n different subproblems. Cache them and each is solved once, with k work for its loop.

Algorithm.

  1. Create dp of size n filled with -1 (costs are never negative).
  2. In the helper, return the cached value when present; otherwise run the loop from Approach 1 and store the result.
static int memoization(int[] h, int k) {
    int[] dp = new int[h.length];
    Arrays.fill(dp, -1);
    return memo(h.length - 1, h, k, dp);
}

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

Complexity. Time O(n · k): n states, k transitions each. Space O(n) for the table plus O(n) stack, which is too deep for Java’s default stack once n reaches tens of thousands.

Approach 3: Tabulation

Intuition. Every f(i) reads only smaller indices, so fill the table from stair 0 upward. By the time we reach i, all of dp[i - k..i - 1] are final.

Algorithm.

  1. dp[0] = 0.
  2. For i from 1 to n - 1: dp[i] = min over valid j of dp[i - j] + |h[i] - h[i - j]|.
  3. Return dp[n - 1].
static int tabulation(int[] h, int k) {
    int n = h.length;
    int[] dp = new int[n];
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        int best = Integer.MAX_VALUE;
        for (int j = 1; j <= k && i - j >= 0; j++) {
            best = Math.min(best, dp[i - j] + Math.abs(h[i] - h[i - j]));
        }
        dp[i] = best;
    }
    return dp[n - 1];
}

Dry run on h = [10, 30, 40, 50, 20], k = 3:

i h[i] j = 1 j = 2 j = 3 dp[i]
0 10 - - - 0
1 30 0 + 20 = 20 - - 20
2 40 20 + 10 = 30 0 + 30 = 30 - 30
3 50 30 + 10 = 40 20 + 20 = 40 0 + 40 = 40 40
4 20 40 + 30 = 70 30 + 20 = 50 20 + 10 = 30 30

The answer dp[4] = 30 comes from the jump of length 3 out of stair 1.

Complexity. Time O(n · k), space O(n).

Approach 4: Ring buffer

Intuition. In plain Frog Jump we kept two variables because dp[i] read only the last two cells. Here it reads the last k cells, so keep exactly those. A ring buffer of size k stores dp[i] at position i % k. When we are about to write dp[i] into slot i % k, that slot holds dp[i - k], the oldest value the current step needed, and it has already been read because the loop finishes before the write. So the overwrite is safe.

If k ≥ n, a buffer of size n is enough, since no stair index reaches n; the code uses size = min(n, k).

Algorithm.

  1. size = min(n, k), ring[0] = 0.
  2. For i from 1 to n - 1: compute best by reading ring[(i - j) % size] for each valid j, then write ring[i % size] = best.
  3. Return ring[(n - 1) % size].
static int ringBuffer(int[] h, int k) {
    int n = h.length;
    int size = Math.min(n, k);
    int[] ring = new int[size];                             // ring[i % size] holds dp[i]
    ring[0] = 0;
    for (int i = 1; i < n; i++) {
        int best = Integer.MAX_VALUE;
        for (int j = 1; j <= k && i - j >= 0; j++) {
            best = Math.min(best, ring[(i - j) % size] + Math.abs(h[i] - h[i - j]));
        }
        ring[i % size] = best;                              // overwrites dp[i - size], which is no longer needed
    }
    return ring[(n - 1) % size];
}

Complexity. Time O(n · k), space O(min(n, k)). This only matters when k is much smaller than n; in interviews the tabulation is the expected answer and the ring buffer is a follow-up.

You might hope for something faster than O(n · k), as in “sliding window minimum” problems. That trick needs the cost of a jump to depend on only one endpoint. Here the cost |h[i] - h[j]| mixes both stairs, so the minimum over the window changes with i. With small k, O(n · k) is the standard solution.

Edge cases and pitfalls