Frog Jump

Find minimum energy to spent by frog to reach at last.

Frog Jump

Problem Statement

A frog wants to climb a staircase with n steps. You're given an integer array, heights, where heights[i] is the height of the ith step.

To jump from step i to step j, the frog uses abs(heights[i] - heights[j]) energy, where abs() means the absolute difference. From any step i, the frog can jump either one step forward (i + 1) or two steps forward (i + 2), as long as that step exists.

Return the minimum amount of energy needed for the frog to go from step 0 to step n - 1.

Examples

Example 1

Input: heights = [2, 1, 3, 5, 4]

Output: 2

Explanation:

One possible route:

• Step 0 → Step 2 = abs(2 - 3) = 1
• Step 2 → Step 4 = abs(3 - 4) = 1

Total = 1 + 1 = 2.

Example 2

Input: heights = [7, 5, 1, 2, 6]

Output: 9

Explanation:

One possible route:

• Step 0 → Step 1 = abs(7 - 5) = 2
• Step 1 → Step 3 = abs(5 - 2) = 3
• Step 3 → Step 4 = abs(2 - 6) = 4

Total = 2 + 3 + 4 = 9.

Solution

This problem can be solved in four progressive steps, each one building on the last to improve efficiency — starting from plain recursion, all the way to a space-optimized version.

1. Brute Force (Plain Recursion)

For every step, the frog has two choices: jump one step forward, or jump two steps forward (if possible). We try both, and take whichever leads to less total energy.

• If we're at step n, we calculate the cost of coming from step n - 1 (a one-step jump) and from step n - 2 (a two-step jump, if n > 1).
• We recursively solve for both of these smaller cases, and return the smaller total energy between the two options.

frogJump(heights) {
    function recurr(n) {
      if (n == 0) return 0;

      let left = recurr(n - 1) + Math.abs(heights[n] - heights[n - 1]);
      let right = Infinity;
      if (n > 1) right = recurr(n - 2) + Math.abs(heights[n] - heights[n - 2]);

      return Math.min(right, left);
    }

    return recurr(heights.length - 1);
}

This works, but it recalculates the same subproblems many times, making it inefficient for larger inputs.

2. Memoization (Top-Down)

We use the same recursive approach as above, but this time, we store the result for each step in a memo array the first time we calculate it. If we're ever asked for that same step's result again, we just look it up instead of recalculating it.

frogJump(heights) {
    function recurr(n, memo) {
      if (n == 0) return 0;
      if (memo[n] !== undefined) {
        return memo[n];
      }
      let left = recurr(n - 1, memo) + Math.abs(heights[n] - heights[n - 1]);
      let right = Infinity;
      if (n > 1)
        right = recurr(n - 2, memo) + Math.abs(heights[n] - heights[n - 2]);
      memo[n] = Math.min(right, left);
      return Math.min(right, left);
    }

    return recurr(heights.length - 1, []);
}

3. Tabulation (Bottom-Up)

Instead of starting from the last step and working backward with recursion, we start from the first step and build our way forward, filling in a dp array as we go.

• dp[i] holds the minimum energy needed to reach step i.
• For each step, we calculate the cost of arriving from one step back, and (if possible) from two steps back, and take the smaller of the two.

frogJump(heights) {
    let dp = [];
    let n = heights.length;

    dp.push(0);

    for (let i = 1; i < n; i++) {
      let fs = dp[i - 1] + Math.abs(heights[i] - heights[i - 1]);
      let ss = Infinity;

      if (i > 1) {
        ss = dp[i - 2] + Math.abs(heights[i] - heights[i - 2]);
      }

      dp[i] = Math.min(fs, ss);
    }

    return dp[n - 1];
}

4. Space Optimization

Looking at the tabulation approach, we notice that to calculate dp[i], we only ever need the results from the two previous steps — dp[i-1] and dp[i-2]. We don't need to keep the entire array around.

So instead of an array, we just track the two most recent results using two variables, prev1 and prev2, updating them as we move forward.

frogJump(heights) {
    let n = heights.length;

    let prev1 = 0;
    let prev2 = 0;

    for (let i = 1; i < n; i++) {
      let fs = prev1 + Math.abs(heights[i] - heights[i - 1]);
      let ss = Infinity;

      if (i > 1) {
        ss = prev2 + Math.abs(heights[i] - heights[i - 2]);
      }

      let curr = Math.min(fs, ss);

      prev2 = prev1;
      prev1 = curr;
    }

    return prev1;
}