☕ DSA Java Articles

Topics › Dynamic Programming › 1D DP

Frog Jump

Medium TUF ID 288 A2Z

Java source ↗ Edit this article ↗

Problem

There are n stairs, and stair i has height h[i]. A frog starts on stair 0 and wants to reach stair n - 1. From stair i it can jump to stair i + 1 or stair i + 2. A jump from stair i to stair j costs |h[i] - h[j]| energy. Return the minimum total energy needed to reach the last stair.

Constraints (the Coding Ninjas version used by the sheet): 1 ≤ n ≤ 10^5, 0 ≤ h[i] ≤ 10^4. The worst total is below 10^9, so int is enough. This is not LeetCode 403, which shares the name but is a different problem about stones in a river.

Example 1

h = [10, 20, 30, 10]
answer = 20         // 0 -> 1 costs 10, then 1 -> 3 costs |20 - 10| = 10

Example 2

h = [10, 50, 10]
answer = 0          // jump 0 -> 2 directly, both heights are 10

Why greedy fails

The tempting approach is to always take the cheaper of the two next jumps. On h = [30, 10, 60, 10, 60, 50] greedy goes 0 -> 1 (cost 20, cheaper than 30), then 1 -> 3 (cost 0), then 3 -> 5 (cost 40), total 60. The best route is 0 -> 2 -> 4 -> 5 with cost 30 + 0 + 10 = 40. Paying more on the first jump put the frog on a stair from which the rest of the climb was cheap. A locally cheap jump can lead somewhere expensive, so we have to compare all routes, and DP is how we do that without enumerating them.

Approach 1: Recursion

Intuition. Let f(i) be the minimum energy to reach stair i from stair 0. The frog arrives at stair i by exactly one last jump, either from i - 1 or from i - 2. Whichever it was, the route up to that earlier stair should itself be the cheapest possible, because the cost of the remaining jump does not depend on how the frog got there. So

f(0) = 0
f(i) = min( f(i - 1) + |h[i] - h[i - 1]|,
            f(i - 2) + |h[i] - h[i - 2]| )      // second option only when i ≥ 2

The answer is f(n - 1). This “the best route to i is built from the best route to an earlier stair” property is exactly the optimal substructure that DP needs.

Algorithm.

  1. If i == 0, return 0.
  2. one = f(i - 1) + |h[i] - h[i - 1]|.
  3. two = f(i - 2) + |h[i] - h[i - 2]| if i > 1, otherwise “infinity”.
  4. Return min(one, two).
static int recursive(int[] h) {
    return solve(h.length - 1, h);
}

static int solve(int i, int[] h) {
    if (i == 0) return 0;                                   // already standing on stair 0
    int one = solve(i - 1, h) + Math.abs(h[i] - h[i - 1]);  // last jump came from i - 1
    int two = Integer.MAX_VALUE;
    if (i > 1) two = solve(i - 2, h) + Math.abs(h[i] - h[i - 2]); // last jump came from i - 2
    return Math.min(one, two);
}

Complexity. Time O(2^n): two branches per call, with the same stairs re-solved over and over. Space O(n) for the recursion depth.

The “infinity” is Integer.MAX_VALUE, and it is only ever compared, never added to. Adding anything to it would overflow into a negative number and win every min.

Approach 2: Memoization

Intuition. f(i) depends only on i, so there are n distinct states. Cache each one.

Algorithm.

  1. Create dp of size n, filled with -1. Real costs are never negative, so -1 cannot be confused with an answer.
  2. In the helper, after the base case, return dp[i] if it is filled; otherwise compute it as in Approach 1 and store it.
static int memoization(int[] h) {
    int[] dp = new int[h.length];
    Arrays.fill(dp, -1);                                    // -1 = not computed (real costs are >= 0)
    return memo(h.length - 1, h, dp);
}

static int memo(int i, int[] h, int[] dp) {
    if (i == 0) return 0;
    if (dp[i] != -1) return dp[i];
    int one = memo(i - 1, h, dp) + Math.abs(h[i] - h[i - 1]);
    int two = Integer.MAX_VALUE;
    if (i > 1) two = memo(i - 2, h, dp) + Math.abs(h[i] - h[i - 2]);
    return dp[i] = Math.min(one, two);
}

Complexity. Time O(n), space O(n) for the table plus O(n) recursion stack. With n = 10^5, that stack depth will overflow Java’s default thread stack, which is the practical reason to move on to tabulation.

Approach 3: Tabulation

Intuition. f(i) only depends on smaller indices, so compute dp[0], dp[1], ..., dp[n - 1] in order. Each cell is one comparison.

Algorithm.

  1. dp[0] = 0.
  2. For i from 1 to n - 1, set dp[i] to the minimum of dp[i - 1] + |h[i] - h[i - 1]| and, when i > 1, dp[i - 2] + |h[i] - h[i - 2]|.
  3. Return dp[n - 1].
static int tabulation(int[] h) {
    int n = h.length;
    int[] dp = new int[n];
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        int one = dp[i - 1] + Math.abs(h[i] - h[i - 1]);
        int two = Integer.MAX_VALUE;
        if (i > 1) two = dp[i - 2] + Math.abs(h[i] - h[i - 2]);
        dp[i] = Math.min(one, two);
    }
    return dp[n - 1];
}

Dry run on h = [30, 10, 60, 10, 60, 50], the input that fools greedy:

i h[i] from i - 1 from i - 2 dp[i]
0 30 - - 0
1 10 0 + 20 = 20 - 20
2 60 20 + 50 = 70 0 + 30 = 30 30
3 10 30 + 50 = 80 20 + 0 = 20 20
4 60 20 + 50 = 70 30 + 0 = 30 30
5 50 30 + 10 = 40 20 + 40 = 60 40

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

Approach 4: Space optimized

Intuition. Computing dp[i] reads dp[i - 1] and dp[i - 2] and nothing older. Two variables are enough: prev for dp[i - 1] and prev2 for dp[i - 2].

Algorithm.

  1. prev = prev2 = 0.
  2. For i from 1 to n - 1: compute cur exactly as in tabulation using prev and prev2, then shift prev2 = prev, prev = cur.
  3. Return prev. With one stair the loop does not run and the answer is 0.

At i = 1, prev2 is a placeholder that is never used, because the i > 1 guard skips the two-step option.

static int spaceOptimized(int[] h) {
    int prev2 = 0, prev = 0;                                // dp[i - 2] and dp[i - 1]
    for (int i = 1; i < h.length; i++) {
        int one = prev + Math.abs(h[i] - h[i - 1]);
        int two = Integer.MAX_VALUE;
        if (i > 1) two = prev2 + Math.abs(h[i] - h[i - 2]);
        int cur = Math.min(one, two);
        prev2 = prev;
        prev = cur;
    }
    return prev;
}

Complexity. Time O(n), space O(1).

Edge cases and pitfalls