Given an integer array height[] where height[i] represents the height of the i-th stair, a frog starts from the first stair and wants to reach the last stair. From any stair i, the frog has two options: it can either jump to the (i+1)-th stair or the (i+2)-th stair. The cost of a jump is the absolute difference in height between the two stairs. Find the minimum total cost required for the frog to reach the last stair.
Examples:
Input: heights[] = [20, 30, 40, 20]
Output: 20
Explanation: Minimum cost is incurred when the frog jumps from stair 0 to 1 then 1 to 3:
jump from stair 0 to 1: cost = |30 - 20| = 10
jump from stair 1 to 3: cost = |20 - 30| = 10
Total Cost = 10 + 10 = 20Input: heights[] = [30, 20, 50, 10, 40]
Output: 30
Explanation: Minimum cost will be incurred when frog jumps from stair 0 to 2 then 2 to 4:
jump from stair 0 to 2: cost = |50 - 30| = 20
jump from stair 2 to 4: cost = |40 - 50| = 10
Total Cost = 20 + 10 = 30
Try it on GfG Practice
This problem is mainly a variation of finding n-th Fibonacci Number. Here we have costs also associated with the two previous numbers.
Table of Content
[Naive Approach] - Using Recursion – O(2^n) Time and O(n) Space
In this approach, we observe that to reach the nth stair, one can come either from the (n−1)th or (n−2)th stair. So, in order to compute the minimum cost to reach the nth stair, we must know the minimum cost to reach the (n−1)th and (n−2)th stairs. Similarly, in order to compute the minimum cost to reach the (n-1)th stair, we must know the minimum cost to reach the (n−2)th and (n−3)th stairs. This way we can observe that this can be done using recursion.
//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends
int minCostRec(int n, vector<int>& height) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return abs(height[n] - height[n - 1]);
return min(
minCostRec(n - 1, height) + abs(height[n] - height[n - 1]),
minCostRec(n - 2, height) + abs(height[n] - height[n - 2])
);
}
int minCost(vector<int>& height) {
int n = height.size();
return minCostRec(n - 1, height);
}
//Driver Code Starts
int main() {
vector<int> height = {20, 30, 40, 20};
cout << minCost(height);
}
//Driver Code Ends
//Driver Code Starts
#include <stdio.h>
#include <stdlib.h>
//Driver Code Ends
int minCostRec(int n, int height[]) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return abs(height[n] - height[n - 1]);
return min(
minCostRec(n - 1, height) + abs(height[n] - height[n - 1]),
minCostRec(n - 2, height) + abs(height[n] - height[n - 2])
);
}
int minCost(int height[], int n) {
return minCostRec(n - 1, height);
}
//Driver Code Starts
int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int height[] = {20, 30, 40, 20};
int n = sizeof(height)/sizeof(height[0]);
printf("%d
", minCost(height, n));
}
//Driver Code Ends
//Driver Code Starts
import static java.lang.Math.min;
import static java.lang.Math.abs;
class GFG {
//Driver Code Ends
static int minCostRec(int n, int[] height) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return abs(height[n] - height[n - 1]);
return min(minCostRec(n -1, height)
+ abs(height[n] - height[n - 1]),
minCostRec(n - 2, height)
+ abs(height[n] - height[n - 2]));
}
static int minCost(int[] height) {
int n = height.length;
return minCostRec(n-1, height);
}
//Driver Code Starts
public static void main(String[] args) {
int[] height = {20, 30, 40, 20};
System.out.println(minCost(height));
}
}
//Driver Code Ends
def minCostRec(n, height):
# If there is only one
# stair(0-based index)
if n == 0:
return 0
# If there are only 2 stairs(0-based
# index), then frog can only take
# jump of size one
if n == 1:
return abs(height[n] - height[n - 1])
return min(
minCostRec(n - 1, height) + abs(height[n] - height[n - 1]),
minCostRec(n - 2, height) + abs(height[n] - height[n - 2])
)
def minCost(height):
n = len(height)
return minCostRec(n - 1, height)
#Driver Code Starts
height = [20, 30, 40, 20]
print(minCost(height))
#Driver Code Ends
//Driver Code Starts
using static System.Math;
using System;
class GFG {
//Driver Code Ends
static int minCostRec(int n, int[] height) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return Abs(height[n] - height[n - 1]);
return Min(
minCostRec(n - 1, height) + Abs(height[n] - height[n - 1]),
minCostRec(n - 2, height) + Abs(height[n] - height[n - 2])
);
}
static int minCost(int[] height) {
int n = height.Length;
return minCostRec(n - 1, height);
}
//Driver Code Starts
public static void Main() {
int[] height = {20, 30, 40, 20};
Console.WriteLine(minCost(height));
}
}
//Driver Code Ends
function minCostRec(n, height) {
// If there is only one
// stair(0-based index)
if (n === 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n === 1)
return Math.abs(height[n] - height[n - 1]);
return Math.min(
minCostRec(n - 1, height) + Math.abs(height[n] - height[n - 1]),
minCostRec(n - 2, height) + Math.abs(height[n] - height[n - 2])
);
}
function minCost(height) {
let n = height.length;
return minCostRec(n - 1, height);
}
//Driver Code Starts
let height = [20, 30, 40, 20];
console.log(minCost(height));
//Driver Code Ends
Output
20
[Better Approach - 1] - Using Memoization – O(n) Time and O(n) Space
In this approach, we notice that the same subproblems are being computed multiple times.
For example, minCost(n) calls minCost(n-1) and minCost(n-2), and minCost(n-1) again calls minCost(n-2) and minCost(n-3).
Here, minCost(n-2) is computed more than once. To avoid this redundant computation, we can store the results of subproblems in a dp array and reuse them whenever needed.
//Driver Code Starts
#include <vector>
#include <iostream>
using namespace std;
//Driver Code Ends
int minCostRec(int n, vector<int>& height, vector<int>& dp) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return abs(height[n] - height[n - 1]);
// if the result for this subproblem is
// already computed then return it
if (dp[n] != -1)
return dp[n];
dp[n] = min(
minCostRec(n - 1, height, dp) + abs(height[n] - height[n - 1]),
minCostRec(n - 2, height, dp) + abs(height[n] - height[n - 2])
);
return dp[n];
}
int minCost(vector<int>& height) {
int n = height.size();
// filling dp array with invalid values
vector<int> dp(n + 1, -1);
return minCostRec(n-1, height, dp);
}
//Driver Code Starts
int main() {
vector<int> height = {20, 30, 40, 20};
cout << minCost(height);
}
//Driver Code Ends
//Driver Code Starts
#include <stdio.h>
#include <stdlib.h>
//Driver Code Ends
int minCostRec(int n, int height[], int dp[]) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return abs(height[n] - height[n - 1]);
// if the result for this subproblem is
// already computed then return it
if (dp[n] != -1)
return dp[n];
int cost1 = minCostRec(n - 1, height, dp) + abs(height[n] - height[n - 1]);
int cost2 = minCostRec(n - 2, height, dp) + abs(height[n] - height[n - 2]);
dp[n] = (cost1 < cost2) ? cost1 : cost2;
return dp[n];
}
int minCost(int height[], int n) {
int* dp = (int*)malloc((n + 1) * sizeof(int));
// filling dp array with invalid values
for (int i = 0; i <= n; i++) dp[i] = -1;
int res = minCostRec(n-1, height, dp);
free(dp);
return res;
}
//Driver Code Starts
int main() {
int height[] = {20, 30, 40, 20};
int n = sizeof(height)/sizeof(height[0]);
printf("%d
", minCost(height, n));
}
//Driver Code Ends
//Driver Code Starts
import static java.lang.Math.abs;
import static java.lang.Math.min;
import java.util.Arrays;
class GFG {
//Driver Code Ends
static int minCostRec(int n, int[] height, int[] dp) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return abs(height[n] - height[n - 1]);
// if the result for this subproblem is
// already computed then return it
if (dp[n] != -1)
return dp[n];
dp[n] = min(
minCostRec(n - 1, height, dp) + abs(height[n] - height[n - 1]),
minCostRec(n - 2, height, dp) + abs(height[n] - height[n - 2])
);
return dp[n];
}
static int minCost(int[] height) {
int n = height.length;
int[] dp = new int[n + 1];
// filling dp array with invalid values
Arrays.fill(dp, -1);
return minCostRec(n-1, height, dp);
}
//Driver Code Starts
public static void main(String[] args) {
int[] height = {20, 30, 40, 20};
System.out.println(minCost(height));
}
}
//Driver Code Ends
def minCostRec(n, height, dp):
# If there is only one
# stair(0-based index)
if n == 0:
return 0
# If there are only 2 stairs(0-based
# index), then frog can only take
# jump of size one
if n == 1:
return abs(height[n] - height[n - 1])
# if the result for this subproblem is
# already computed then return it
if dp[n] != -1:
return dp[n]
dp[n] = min(
minCostRec(n - 1, height, dp) + abs(height[n] - height[n - 1]),
minCostRec(n - 2, height, dp) + abs(height[n] - height[n - 2])
)
return dp[n]
def minCost(height):
n = len(height)
# filling dp array with invalid values
dp = [-1] * (n + 1)
return minCostRec(n-1, height, dp)
#Driver Code Starts
height = [20, 30, 40, 20]
print(minCost(height))
#Driver Code Ends
//Driver Code Starts
using System;
using static System.Math;
class GFG {
//Driver Code Ends
static int minCostRec(int n, int[] height, int[] dp) {
// If there is only one
// stair(0-based index)
if (n == 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n == 1)
return Math.Abs(height[n] - height[n - 1]);
// if the result for this subproblem is
// already computed then return it
if (dp[n] != -1)
return dp[n];
dp[n] = Min(
minCostRec(n - 1, height, dp) + Abs(height[n] - height[n - 1]),
minCostRec(n - 2, height, dp) + Abs(height[n] - height[n - 2])
);
return dp[n];
}
static int minCost(int[] height) {
int n = height.Length;
int[] dp = new int[n + 1];
// filling dp array with invalid values
for (int i = 0; i <= n; i++) dp[i] = -1;
return minCostRec(n-1, height, dp);
}
//Driver Code Starts
public static void Main() {
int[] height = {20, 30, 40, 20};
Console.WriteLine(minCost(height));
}
}
//Driver Code Ends
function minCostRec(n, height, dp) {
// If there is only one
// stair(0-based index)
if (n === 0)
return 0;
// If there are only 2 stairs(0-based
// index), then frog can only take
// jump of size one
if (n === 1)
return Math.abs(height[n] - height[n - 1]);
// if the result for this subproblem is
// already computed then return it
if (dp[n] !== -1)
return dp[n];
dp[n] = Math.min(
minCostRec(n - 1, height, dp) + Math.abs(height[n] - height[n - 1]),
minCostRec(n - 2, height, dp) + Math.abs(height[n] - height[n - 2])
);
return dp[n];
}
function minCost(height) {
const n = height.length;
// filling dp array with invalid values
const dp = new Array(n + 1).fill(-1);
return minCostRec(n-1, height, dp);
}
//Driver Code Starts
const height = [20, 30, 40, 20];
console.log(minCost(height));
//Driver Code Ends
Output
20
[Better Approach - 2] - Using Bottom-Up DP (Tabulation) – O(n) Time and O(n) Space
In this approach, we iteratively calculate the answers starting with the smallest subproblems — the first two stairs. Since larger subproblems depend on smaller ones, we solve the smaller subproblems first. Using answers to these smaller subproblems, we then find the answers for subsequent larger subproblems one by one. Each new value is computed using the results of the previous two (which have already been calculated) and stored for further calculations.
//Driver Code Starts
#include <vector>
#include <iostream>
using namespace std;
//Driver Code Ends
int minCost(vector<int>& height) {
int n = height.size();
// DP array to store the minimum cost
vector<int> dp(n);
// If there is only one stair,
// cost will be zero
dp[0] = 0;
// If there are 2 stairs, then frog
// can only take jump of size one
if (n > 1) dp[1] = abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
dp[i] = min(dp[i - 1] + abs(height[i] - height[i - 1]),
dp[i - 2] + abs(height[i] - height[i - 2]));
}
return dp[n - 1];
}
//Driver Code Starts
int main() {
vector<int> height = {20, 30, 40, 20};
cout << minCost(height);
}
//Driver Code Ends
//Driver Code Starts
#include <stdio.h>
#include <stdlib.h>
int min(int a, int b) {
return (a < b) ? a : b;
}
//Driver Code Ends
int minCost(int height[], int n) {
// DP array to store the minimum cost
int* dp = (int*)malloc(n * sizeof(int));
// If there is only one stair,
// cost will be zero
dp[0] = 0;
// If there are 2 stairs, then frog
// can only take jump of size one
if (n > 1) dp[1] = abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
dp[i] = min(dp[i - 1] + abs(height[i] - height[i - 1]),
dp[i - 2] + abs(height[i] - height[i - 2]));
}
int result = dp[n - 1];
free(dp);
return result;
}
//Driver Code Starts
int main() {
int height[] = {20, 30, 40, 20};
int n = sizeof(height)/sizeof(height[0]);
printf("%d
", minCost(height, n));
}
//Driver Code Ends
//Driver Code Starts
import static java.lang.Math.abs;
import static java.lang.Math.min;
class GFG {
//Driver Code Ends
static int minCost(int[] height) {
int n = height.length;
// DP array to store the minimum cost
int[] dp = new int[n];
// If there is only one stair,
// cost will be zero
dp[0] = 0;
// If there are 2 stairs, then frog
// can only take jump of size one
if( n > 1) dp[1] = abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
dp[i] = min(dp[i - 1] + abs(height[i] - height[i - 1]),
dp[i - 2] + abs(height[i] - height[i - 2]));
}
return dp[n-1];
}
//Driver Code Starts
public static void main(String[] args) {
int[] height = {20, 30, 40, 20};
System.out.println(minCost(height));
}
}
//Driver Code Ends
def minCost(height):
n = len(height)
# DP array to store the minimum cost
dp = [0] * n
# If there is only one stair,
# cost will be zero
dp[0] = 0
# If there are 2 stairs, then frog
# can only take jump of size one
if n > 1:
dp[1] = abs(height[1] - height[0])
for i in range(2, n):
dp[i] = min(dp[i - 1] + abs(height[i] - height[i - 1]),
dp[i - 2] + abs(height[i] - height[i - 2]))
return dp[n - 1]
#Driver Code Starts
height = [20, 30, 40, 20]
print(minCost(height))
#Driver Code Ends
//Driver Code Starts
using System;
class GFG {
//Driver Code Ends
static int minCost(int[] height) {
int n = height.Length;
// DP array to store the minimum cost
int[] dp = new int[n];
// If there is only one stair,
// cost will be zero
dp[0] = 0;
// If there are 2 stairs, then frog
// can only take jump of size one
if (n > 1) dp[1] = Math.Abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
dp[i] = Math.Min(dp[i - 1] + Math.Abs(height[i] - height[i - 1]),
dp[i - 2] + Math.Abs(height[i] - height[i - 2]));
}
return dp[n - 1];
}
//Driver Code Starts
public static void Main() {
int[] height = {20, 30, 40, 20};
Console.WriteLine(minCost(height));
}
}
//Driver Code Ends
function minCost(height) {
const n = height.length;
// DP array to store the minimum cost
const dp = new Array(n);
// If there is only one stair,
// cost will be zero
dp[0] = 0;
// If there are 2 stairs, then frog
// can only take jump of size one
if (n > 1) dp[1] = Math.abs(height[1] - height[0]);
for (let i = 2; i < n; i++) {
dp[i] = Math.min(dp[i - 1] + Math.abs(height[i] - height[i - 1]),
dp[i - 2] + Math.abs(height[i] - height[i - 2]));
}
return dp[n - 1];
}
//Driver Code Starts
const height = [20, 30, 40, 20];
console.log(minCost(height));
//Driver Code Ends
Output
20
[Expected Approach] - Using Space Optimized DP – O(n) Time and O(1) Space
In this approach, we observe that in order to find solution for a particular state, we only need the answer for just two previous states. Hence, we can store the results for the previous two states, and as we move forward, we keep updating them to compute the next values. This means keeping track of the last two states and using them to calculate the next one will help us to find the solution optimally, without using extra space.
//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends
int minCost(vector<int> &height) {
int n = height.size();
if(n == 1)
return 0;
// Variables prev1 and prev2 to store the result
// of last and second last states
int prev2 = 0;
int prev1 = abs(height[1] - height[0]);
for(int i = 2; i < n; i++) {
int curr = min(prev1 + abs(height[i] - height[i - 1]),
prev2 + abs(height[i] - height[i - 2]));
// Updating prev2 to previous result and
// prev1 to current result
prev2 = prev1;
prev1 = curr;
}
// In the last iteration, final value
// of curr is stored in prev1
return prev1;
}
//Driver Code Starts
int main() {
vector<int> height = {20, 30, 40, 20};
cout << minCost(height);
return 0;
}
//Driver Code Ends
//Driver Code Starts
#include <stdio.h>
#include <stdlib.h>
//Driver Code Ends
int minCost(int height[], int n) {
if (n == 1)
return 0;
// Variables prev1 and prev2 to store the result
// of last and second last states
int prev2 = 0;
int prev1 = abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
int curr = (prev1 + abs(height[i] - height[i - 1]) <
prev2 + abs(height[i] - height[i - 2]))
? (prev1 + abs(height[i] - height[i - 1]))
: (prev2 + abs(height[i] - height[i - 2]));
// Updating prev2 to previous result and
// prev1 to current result
prev2 = prev1;
prev1 = curr;
}
// In the last iteration, final value
// of curr is stored in prev1
return prev1;
}
//Driver Code Starts
int main() {
int height[] = {20, 30, 40, 20};
int n = sizeof(height) / sizeof(height[0]);
printf("%d", minCost(height, n));
return 0;
}
//Driver Code Ends
//Driver Code Starts
import static java.lang.Math.min;
import static java.lang.Math.abs;
class GFG {
//Driver Code Ends
static int minCost(int[] height) {
int n = height.length;
if (n == 1)
return 0;
// Variables prev1 and prev2 to store the result
// of last and second last states
int prev2 = 0;
int prev1 = Math.abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
int curr = Math.min(prev1 + Math.abs(height[i] - height[i-1]),
prev2 + Math.abs(height[i] - height[i-2]));
// Updating prev2 to previous result and
// prev1 to current result
prev2 = prev1;
prev1 = curr;
}
// In the last iteration, final value
// of curr is stored in prev1
return prev1;
}
//Driver Code Starts
public static void main(String[] args) {
int[] height = new int[]{20, 30, 40, 20};
System.out.println(minCost(height));
}
}
//Driver Code Ends
def minCost(height):
n = len(height)
if n == 1:
return 0
# Variables prev1 and prev2 to store the result
# of last and second last states
prev2 = 0
prev1 = abs(height[1] - height[0])
for i in range(2, n):
curr = min(prev1 + abs(height[i] - height[i - 1]),
prev2 + abs(height[i] - height[i - 2]))
# Updating prev2 to previous result and
# prev1 to current result
prev2 = prev1
prev1 = curr
# In the last iteration, final value
# of curr is stored in prev1
return prev1
#Driver Code Starts
height = [20, 30, 40, 20]
print(minCost(height))
#Driver Code Ends
//Driver Code Starts
using System;
class GFG {
//Driver Code Ends
static int minCost(int[] height) {
int n = height.Length;
if (n == 1)
return 0;
// Variables prev1 and prev2 to store the result
// of last and second last states
int prev2 = 0;
int prev1 = Math.Abs(height[1] - height[0]);
for (int i = 2; i < n; i++) {
int curr = Math.Min(prev1 + Math.Abs(height[i] - height[i - 1]),
prev2 + Math.Abs(height[i] - height[i - 2]));
// Updating prev2 to previous result and
// prev1 to current result
prev2 = prev1;
prev1 = curr;
}
// In the last iteration, final value
// of curr is stored in prev1
return prev1;
}
//Driver Code Starts
static void Main() {
int[] height = { 20, 30, 40, 20 };
Console.WriteLine(minCost(height));
}
}
//Driver Code Ends
function minCost(height) {
const n = height.length;
if (n === 1)
return 0;
// Variables prev1 and prev2 to store the result
// of last and second last states
let prev2 = 0;
let prev1 = Math.abs(height[1] - height[0]);
for (let i = 2; i < n; i++) {
let curr = Math.min(prev1 + Math.abs(height[i] - height[i - 1]),
prev2 + Math.abs(height[i] - height[i - 2]));
// Updating prev2 to previous result and
// prev1 to current result
prev2 = prev1;
prev1 = curr;
}
// In the last iteration, final value
// of curr is stored in prev1
return prev1;
}
//Driver Code Starts
const height = [20, 30, 40, 20];
console.log(minCost(height));
//Driver Code Ends
Output
20