Frog Jump: Minimum Energy Using Dynamic Programming

63k
0

An array heights contains the height of every stair. A frog starts at index 0 and must reach index n - 1.

From any stair, either a 1-step jump or a 2-step jump can be made when the destination exists. A jump from one stair to another costs the absolute difference between both heights. Return the minimum total energy required to reach the final stair.

Example 1

Input: heights = [10, 20, 30, 10]
Output: 20
Explanation: The route 0 -> 1 -> 3 costs |10 - 20| + |20 - 10| = 10 + 10 = 20.

Example 2

Input: heights = [7]
Output: 0
Explanation: The starting stair already equals the final stair, so no energy is required.

Recursion

Reaching the final stair can be viewed through the final jump. A final 1-step jump must begin at the previous stair, while a final 2-step jump must begin two stairs earlier. Both starting points contain a smaller version of the same minimum-energy problem.

The same choice appears again at every earlier stair, so recursion fits the repeated decision structure. A recursive function is needed to answer one clear question: the minimum energy required to reach a given index. The state solve(index) represents the required minimum energy. The first helper call uses solve(n - 1) because the final stair is the destination, and the helper works backward through earlier jump choices.

For every state, recursion calculates the complete cost of a 1-step jump and a valid 2-step jump. The smaller complete cost becomes the answer for the current stair. Direct recursion explores every valid route, but repeated calculations make the approach slow for large arrays.

Algorithm

  • Define solve(index) as the minimum energy needed to reach stair index, so every recursive call answers the same smaller problem.

  • Return 0 at index 0 because the starting stair requires no jump and contributes no energy.

  • Calculate the 1-step jump from solve(index - 1) and the matching height difference because every positive index can be reached from the previous stair.

  • Keep the 2-step jump cost at infinity near the start because no valid stair exists two positions earlier.

  • Calculate the 2-step jump from solve(index - 2) when index > 1, so the second valid route into the current stair is considered.

  • Return the smaller complete jump cost because the cheaper route gives the minimum energy for the current state.

  • Start with solve(n - 1) because the state for the final stair represents the complete problem.

Dry Run

Diagram 1
1 / 3

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Computes the minimum energy for one stair.
int solve(int index, vector<int>& heights) {
// The starting stair needs no jump.
if (index == 0) {
return 0;
}
// Measure the cost of the final 1-step jump.
int oneStepDifference = abs(heights[index] - heights[index - 1]);
// Add the best cost for the previous stair.
int oneStepJump = solve(index - 1, heights) + oneStepDifference;
// Infinity marks an unavailable 2-step jump.
int twoStepJump = INT_MAX;
// A 2-step jump exists only beyond index one.
if (index > 1) {
// Measure the cost of the final 2-step jump.
int twoStepDifference = abs(heights[index] - heights[index - 2]);
// Add the best cost from two stairs earlier.
twoStepJump = solve(index - 2, heights) + twoStepDifference;
}
// The cheaper complete route gives the state answer.
return min(oneStepJump, twoStepJump);
}
public:
// Returns the minimum energy for the final stair.
int frogJump(vector<int>& heights) {
int n = heights.size();
// Start at the destination to solve the full problem.
return solve(n - 1, heights);
}
};
// Driver code
int main() {
vector<int> heights = {10, 20, 30, 10};
Solution obj;
cout << obj.frogJump(heights) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of stairs, because each state can branch into two recursive calls in the worst case.

Space Complexity: O(N), because the recursion stack can grow to a depth of at most N.

Memoization

Direct recursion calls solve(index) many times for the same index. A dp array stores completed answers. Each dp[index] value represents the minimum energy required to reach stair index.

Before a recursive state is calculated, dp[index] is checked. A stored answer is reused immediately. The recurrence and state meaning remain identical to the recursive approach.

Algorithm

  • Create a dp array of size n filled with -1, so every untouched position clearly marks an uncalculated state.

  • Keep solve(index) as the minimum energy for stair index, preserving the recursive state and jump choices without alteration.

  • Return 0 at index 0, and reuse dp[index] when available because a stored result removes an entire repeated subtree.

  • Calculate the 1-step jump from solve(index - 1) because every positive index has a valid previous stair.

  • Keep the 2-step jump at infinity until index > 1 because no earlier 2-step source exists near the start, then calculate the second valid route.

  • Store the smaller complete cost in dp[index] so later calls for the same stair can return immediately.

  • Start with solve(n - 1) and return the stored result because the final stair represents the complete destination.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Computes and stores the energy for one stair.
int solve(int index, vector<int>& heights, vector<int>& dp) {
// The starting stair needs no jump.
if (index == 0) {
return 0;
}
// A stored answer removes a repeated subtree.
if (dp[index] != -1) {
return dp[index];
}
// Measure the cost of the final 1-step jump.
int oneStepDifference = abs(heights[index] - heights[index - 1]);
// Add the stored or computed previous answer.
int oneStepJump = solve(index - 1, heights, dp) + oneStepDifference;
// Infinity marks an unavailable 2-step jump.
int twoStepJump = INT_MAX;
// A 2-step jump exists only beyond index one.
if (index > 1) {
// Measure the cost of the final 2-step jump.
int twoStepDifference = abs(heights[index] - heights[index - 2]);
// Add the answer from two stairs earlier.
twoStepJump = solve(index - 2, heights, dp) + twoStepDifference;
}
// Cache the cheaper route for later calls.
dp[index] = min(oneStepJump, twoStepJump);
// The cached value answers the current state.
return dp[index];
}
public:
// Returns the minimum energy for the final stair.
int frogJump(vector<int>& heights) {
int n = heights.size();
// Negative values mark uncalculated states.
vector<int> dp(n, -1);
// Start at the destination to solve the full problem.
return solve(n - 1, heights, dp);
}
};
// Driver code
int main() {
vector<int> heights = {10, 20, 30, 10};
Solution obj;
cout << obj.frogJump(heights) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of stairs, because memoization computes each stair state once with constant work per state.

Space Complexity: O(N), because the dp array stores N values and the recursion stack can also grow to a depth of N.

Tabulation

Memoization evaluates states from the final stair toward smaller indices. Tabulation evaluates the same states from the starting stair toward the final stair.

The recursive term solve(index - 1) becomes dp[index - 1], and solve(index - 2) becomes dp[index - 2]. A left-to-right loop guarantees availability of both required earlier values.

Algorithm

  • Create a dp array of size n, so dp[index] can preserve the minimum energy for every completed stair.

  • Set dp[0] to 0 because remaining on the starting stair spends no energy and supplies the base state.

  • Move from index 1 toward n - 1, so both earlier DP states are ready before the current state is evaluated.

  • Calculate the 1-step jump from dp[index - 1] because the previous stair always offers a valid route.

  • Keep the 2-step jump at infinity until index > 1 because no valid 2-step source exists near the start, then read the second route from dp[index - 2].

  • Store the smaller complete jump cost in dp[index] because the cheaper route is the optimal answer for the current stair.

  • Return dp[n - 1] after the loop because the last table entry represents the final destination.

Dry Run

Frog Jump Tabulation

Frog Jump Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum energy with tabulation.
int frogJump(vector<int>& heights) {
int n = heights.size();
// Each position stores one completed stair answer.
vector<int> dp(n, 0);
// Left-to-right order prepares both earlier states.
for (int index = 1; index < n; index++) {
// Measure the cost of the current 1-step jump.
int oneStepDifference = abs(heights[index] - heights[index - 1]);
// Extend the best route from the previous stair.
int oneStepJump = dp[index - 1] + oneStepDifference;
// Infinity marks an unavailable 2-step jump.
int twoStepJump = INT_MAX;
// A 2-step jump exists only beyond index one.
if (index > 1) {
// Measure the cost of the current 2-step jump.
int twoStepDifference = abs(heights[index] - heights[index - 2]);
// Extend the route from two stairs earlier.
twoStepJump = dp[index - 2] + twoStepDifference;
}
// Store the cheaper complete route for this stair.
dp[index] = min(oneStepJump, twoStepJump);
}
// The last table value answers the full problem.
return dp[n - 1];
}
};
// Driver code
int main() {
vector<int> heights = {10, 20, 30, 10};
Solution obj;
cout << obj.frogJump(heights) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of stairs, because each stair is processed once with constant transition work.

Space Complexity: O(N), because the iterative approach stores one dp value for each stair and uses no recursion stack.

Space Optimization

The tabulation transition uses only dp[index - 1] and dp[index - 2]. The variable previous can represent dp[index - 1], while secondPrevious can represent dp[index - 2].

At the beginning of every loop iteration, previous contains the answer for the previous stair and secondPrevious contains the answer from two stairs earlier. Both values are sufficient for calculating current, the answer for the present stair.

After current is calculated, the stored values are shifted forward. The old previous value becomes secondPrevious, and current becomes the new previous. The assignment order preserves the value needed for the next iteration. Older DP values are never read again, so the complete array can be removed.

Algorithm

  • Initialize previous and secondPrevious with 0, so both variables begin from the zero-energy starting state.

  • Move from index 1 toward n - 1, preserving the same dependency order used by tabulation.

  • Calculate the 1-step jump from previous because the variable represents dp[index - 1].

  • Keep the 2-step jump at infinity until index > 1 because no valid 2-step source exists near the start, then use secondPrevious as dp[index - 2].

  • Store the smaller complete jump cost in current because the cheaper route gives the answer for the present stair.

  • Assign previous to secondPrevious before replacing previous, so both values keep the correct meaning for the next index.

  • Return previous after the loop because the final shift stores the destination answer in previous.

Dry Run

Frog Jump Space Optimization

Frog Jump Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum energy with constant space.
int frogJump(vector<int>& heights) {
int n = heights.size();
// Both variables begin at the zero-energy base.
int secondPrevious = 0;
int previous = 0;
// Carry the previous two DP states through the loop.
for (int index = 1; index < n; index++) {
// Measure the cost of the current 1-step jump.
int oneStepDifference = abs(heights[index] - heights[index - 1]);
// Extend the route represented by previous.
int oneStepJump = previous + oneStepDifference;
// Infinity marks an unavailable 2-step jump.
int twoStepJump = INT_MAX;
// A 2-step jump exists only beyond index one.
if (index > 1) {
// Measure the cost of the current 2-step jump.
int twoStepDifference = abs(heights[index] - heights[index - 2]);
// Extend the route from secondPrevious.
twoStepJump = secondPrevious + twoStepDifference;
}
// Current keeps the cheaper complete route.
int current = min(oneStepJump, twoStepJump);
// Shift both state meanings to the next stair.
secondPrevious = previous;
previous = current;
}
// Previous holds the destination answer after the shift.
return previous;
}
};
// Driver code
int main() {
vector<int> heights = {10, 20, 30, 10};
Solution obj;
cout << obj.frogJump(heights) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of stairs, because each stair is processed once with constant transition work.

Space Complexity: O(1), because only a fixed number of energy and difference variables are maintained.

Interview follow-up Questions

No. The starting stair already equals the destination, so the minimum energy equals 0.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0