Given N non-negative integers which signifies the cost of the moving from each stair. Paying the cost at i-th step, you can either climb one or two steps. Given that one can start from the 0-the step or 1-the step, the task is to find the minimum cost to reach the top of the floor(N+1) by climbing N stairs.
Examples:
Input: a[] = { 16, 19, 10, 12, 18 }
Output: 31
Start from 19 and then move to 12.Input: a[] = {2, 5, 3, 1, 7, 3, 4}
Output: 9
2->3->1->3
Minimum cost to reach the top of the floor by climbing stairs using Recursion:
This problem is an extension of problem: Climbing Stairs to reach at the top.
The thing is that we don’t need to go till the last element (since there are all positive numbers then we can avoid climbing to the last element so that we can reduce the cost).
Below is the implementation of the above idea:
C++
// C++ program to find the minimum// cost required to reach the n-th floor#include <bits/stdc++.h>using namespace std;// function to find the minimum cost// to reach N-th floorint minimumCost( int n , int cost[]){ if(n == 0) return cost[0] ; if(n == 1) return cost[1] ; int top = min( minimumCost(n-1,cost) + cost[n] , minimumCost(n-2, cost)+ cost[n] ); return top; }// Driver Codeint main(){ int a[] = { 16, 19, 10, 12, 18 }; int n = sizeof(a) / sizeof(a[0]); cout << minimumCost(n-2, a); return 0;} |
Java
/* Java code for finding minimum cost */import java.io.*;class GFG{ // function to find minimum cost public static int minimumCost(int n, int cost[]){ if(n == 0) return cost[0] ; if(n == 1) return cost[1] ; int top = Math.min( minimumCost(n-1,cost) + cost[n] , minimumCost(n-2, cost)+ cost[n] ); return top; } public static void main (String[] args) { int a[] = { 16, 19, 10, 12, 18 }; int n = a.length; System.out.println(minimumCost(n-2,a)); }}// This code is contributed by rchandra |
Python3
# Python3 program to find# the minimum cost required# to reach the n-th floor# function to find the minimum# cost to reach N-th floordef minimumCost(cost, n): if n == 0: return cost[0] if n == 1: return cost[1] return min(minimumCost(cost, n-1) + cost[n], minimumCost(cost, n-2) + cost[n])# Driver Codeif __name__ == "__main__": a = [16, 19, 10, 12, 18] n = len(a) print(minimumCost(a, n-2)) |
C#
/* C# code for finding minimum cost */using System;class GFG{ // function to find minimum cost public static int minimumCost(int n, int[] cost){ if(n == 0) return cost[0] ; if(n == 1) return cost[1] ; int top = Math.Min( minimumCost(n-1,cost) + cost[n] , minimumCost(n-2, cost)+ cost[n] ); return top; } static public void Main () { int[] a = { 16, 19, 10, 12, 18 }; int n = a.Length; Console.Write(minimumCost(n-2,a)); }}// This code is contributed by Pushpesh Raj. |
Javascript
// Javascript program to find the minimum// cost required to reach the n-th floor// function to find the minimum cost// to reach N-th floorfunction minimumCost(n , cost){ if(n == 0) return cost[0] ; if(n == 1) return cost[1] ; let top = Math.min( minimumCost(n-1,cost) + cost[n] , minimumCost(n-2, cost)+ cost[n] ); return top;}// Driver Code let a = [ 16, 19, 10, 12, 18 ]; let n = a.length; console.log(minimumCost(n-2, a)); // This code is contributed by Aman Kumar |
Output
31
Time Complexity: O(N)
Auxiliary Space: O(1)
Minimum cost to reach the top of the floor by climbing stairs Dynamic Programming (Memoization):
We can store the result of calculated subproblems. So, that we don’t need to recalculate it again.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum// cost required to reach the n-th floor#include <bits/stdc++.h>using namespace std;// function to find the minimum cost// to reach N-th floorint minimumCostMemoized(int n, vector<int>& cost, vector<int>& dp){ if (n == 0) return cost[0]; if (n == 1) return cost[1]; if (dp[n] != -1) return dp[n]; dp[n] = min( minimumCostMemoized(n - 1, cost, dp) + cost[n], minimumCostMemoized(n - 2, cost, dp) + cost[n]); return dp[n];}int minCostClimbingStairs(vector<int>& cost){ int n = cost.size(); vector<int> dp(n + 1, -1); int ans = min(minimumCostMemoized(n - 2, cost, dp), minimumCostMemoized(n - 1, cost, dp)); return ans;}// Driver Codeint main(){ vector<int> a{ 10, 15, 20 }; cout << minCostClimbingStairs(a); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.Arrays;class GFG { // function to find the minimum cost // to reach N-th floor static int minimumCostMemoized(int n, int cost[], int dp[]) { // base case if (n == 0) return dp[n] = cost[0]; if (n == 1) return dp[n] = cost[1]; if (dp[n] != -1) return dp[n]; return dp[n] = Math.min(minimumCostMemoized(n - 1, cost, dp) + cost[n], minimumCostMemoized(n - 2, cost, dp) + cost[n]); } static int minimumCost(int cost[], int n) { int dp[] = new int[n]; Arrays.fill(dp, -1); int top = Math.min( minimumCostMemoized(n - 1, cost, dp), minimumCostMemoized(n - 2, cost, dp)); return top; } public static void main(String[] args) { int a[] = { 10, 15, 20 }; int n = a.length; System.out.println(minimumCost(a, n)); }}// This code is contributed by rchandra. |
Python3
# Python3 program to find# the minimum cost required# to reach the n-th floor# function to find the minimum# cost to reach N-th floordef minimumCostMemoized(n, cost, dp): if n == 0: return cost[0] if n == 1: return cost[1] if dp[n] != -1: return dp[n] dp[n] = min(minimumCostMemoized(n - 1, cost, dp) + cost[n], minimumCostMemoized(n - 2, cost, dp) + cost[n]) return dp[n]def minCostClimbingStairs(cost): n = len(a) dp = [-1]*n ans = min(minimumCostMemoized(n - 2, cost, dp), minimumCostMemoized(n - 1, cost, dp)) return ans# Driver Codeif __name__ == "__main__": a = [16, 19, 10, 12, 18] print(minCostClimbingStairs(a)) |
C#
using System;class GFG { // function to find the minimum cost // to reach N-th floor static int minimumCostMemoized(int n, int[] cost, int[] dp) { // base case if (n == 0) return cost[0]; if (n == 1) return cost[1]; if (dp[n] != -1) return dp[n]; return dp[n] = Math.Min(minimumCostMemoized(n - 1, cost, dp) + cost[n], minimumCostMemoized(n - 2, cost, dp) + cost[n]); } static int minimumCost(int[] cost, int n) { int[] dp = new int[n]; for (int i = 0; i < n; i++) dp[i] = -1; int top = minimumCostMemoized(n - 2, cost, dp); return dp[n - 2]; } public static void Main() { int[] a = { 16, 19, 10, 12, 18 }; int n = a.Length; Console.WriteLine(minimumCost(a, n)); }}// This code is contributed by Utkarsh |
Javascript
// JS program to find the minimum// cost required to reach the n-th floorfunction minimumCostMemoized(n, cost, dp){ // base case for reaching the 0th floor if (n === 0) { return cost[0]; } // base case for reaching the 1st floor if (n === 1) { return cost[1]; } // check if the subproblem is already solved if (dp[n] !== -1) { return dp[n]; } // finding the minimum cost to reach the nth floor dp[n] = Math.min(minimumCostMemoized(n - 1, cost, dp) + cost[n], minimumCostMemoized(n - 2, cost, dp) + cost[n]); return dp[n];}function minCostClimbingStairs(cost) { var n = cost.length; var dp = new Array(n).fill(-1); // finding the minimum cost of reaching n-1 or n-2 floor var ans = Math.min(minimumCostMemoized(n - 2, cost, dp), minimumCostMemoized(n - 1, cost, dp)); return ans;}// Driver Code var a = [16, 19, 10, 12, 18]; console.log(minCostClimbingStairs(a));// This code is contributed by lokeshpotta20. |
Output
15
Time Complexity: O(N)
Auxiliary Space: O(N)
Minimum cost to reach the top of the floor by climbing stairs using Dynamic Programming (Tabulation):
Let dp[i] be the cost to climb the i-th staircase to from 0-th or 1-th step. Hence dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Since dp[i-1] and dp[i-2] are needed to compute the cost of travelling from i-th step, a bottom-up approach can be used to solve the problem. The answer will be the minimum cost of reaching n-1th stair and n-2th stair. Compute the dp[] array in a bottom-up manner.
Below is the implementation of the above approach.
C++
// C++ program to find the minimum// cost required to reach the n-th floor#include <bits/stdc++.h>using namespace std;// function to find the minimum cost// to reach N-th floorint minimumCost(int cost[], int n){ // declare an array int dp[n]; // base case if (n == 1) return cost[0]; // initially to climb till 0-th // or 1th stair dp[0] = cost[0]; dp[1] = cost[1]; // iterate for finding the cost for (int i = 2; i < n; i++) { dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; } // return the minimum return min(dp[n - 2],dp[n-1]);}// Driver Codeint main(){ int a[] = { 16, 19, 10, 12, 18 }; int n = sizeof(a) / sizeof(a[0]); cout << minimumCost(a, n); return 0;} |
Java
// Java program to find the // minimum cost required to// reach the n-th floorimport java.io.*;import java.util.*;class GFG{// function to find // the minimum cost// to reach N-th floorstatic int minimumCost(int cost[], int n){ // declare an array int dp[] = new int[n]; // base case if (n == 1) return cost[0]; // initially to // climb till 0-th // or 1th stair dp[0] = cost[0]; dp[1] = cost[1]; // iterate for finding the cost for (int i = 2; i < n; i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } // return the minimum return Math.min(dp[n - 2], dp[n - 1]);}// Driver Codepublic static void main(String args[]){ int a[] = { 16, 19, 10, 12, 18 }; int n = a.length; System.out.print(minimumCost(a, n));}} |
Python3
# Python3 program to find # the minimum cost required # to reach the n-th floor# function to find the minimum # cost to reach N-th floordef minimumCost(cost, n): # declare an array dp = [None]*n # base case if n == 1: return cost[0] # initially to climb # till 0-th or 1th stair dp[0] = cost[0] dp[1] = cost[1] # iterate for finding the cost for i in range(2, n): dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] # return the minimum return min(dp[n - 2], dp[n - 1])# Driver Codeif __name__ == "__main__": a = [16, 19, 10, 12, 18 ] n = len(a) print(minimumCost(a, n))# This code is contributed # by ChitraNayal |
C#
// C# program to find the // minimum cost required to// reach the n-th floorusing System;class GFG{// function to find // the minimum cost// to reach N-th floorstatic int minimumCost(int[] cost, int n){ // declare an array int []dp = new int[n]; // base case if (n == 1) return cost[0]; // initially to // climb till 0-th // or 1th stair dp[0] = cost[0]; dp[1] = cost[1]; // iterate for finding the cost for (int i = 2; i < n; i++) { dp[i] = Math.Min(dp[i - 1], dp[i - 2]) + cost[i]; } // return the minimum return Math.Min(dp[n - 2], dp[n - 1]);}// Driver Codepublic static void Main(){ int []a = { 16, 19, 10, 12, 18 }; int n = a.Length; Console.WriteLine(minimumCost(a, n));}}// This code is contributed// by Subhadeep |
Javascript
<script>// Javascript program to find the// minimum cost required to// reach the n-th floor // function to find// the minimum cost// to reach N-th floor function minimumCost(cost,n) { // declare an array let dp = new Array(n); // base case if (n == 1) return cost[0]; // initially to // climb till 0-th // or 1th stair dp[0] = cost[0]; dp[1] = cost[1]; // iterate for finding the cost for (let i = 2; i < n; i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } // return the minimum return Math.min(dp[n - 2], dp[n - 1]); } // Driver Code let a=[16, 19, 10, 12, 18 ]; let n = a.length; document.write(minimumCost(a, n)); // This code is contributed by rag2127</script> |
PHP
<?php// PHP program to find the // minimum cost required // to reach the n-th floor// function to find the minimum // cost to reach N-th floorfunction minimumCost(&$cost, $n){ // declare an array // base case if ($n == 1) return $cost[0]; // initially to climb // till 0-th or 1th stair $dp[0] = $cost[0]; $dp[1] = $cost[1]; // iterate for finding // the cost for ($i = 2; $i < $n; $i++) { $dp[$i] = min($dp[$i - 1], $dp[$i - 2]) + $cost[$i]; } // return the minimum return min($dp[$n - 2], $dp[$n - 1]);}// Driver Code$a = array(16, 19, 10, 12, 18);$n = sizeof($a);echo(minimumCost($a, $n)); // This code is contributed// by Shivi_Aggarwal?> |
Output
31
Time Complexity: O(N)
Auxiliary Space: O(N)
Minimum cost to reach the top of the floor by climbing stairs using Dynamic Programming (Space Optimized):
Instead of using dp[] array for memoizing the cost, use two-variable dp1 and dp2. Since the cost of reaching the last two stairs is required only, use two variables and update them by swapping when one stair is climbed.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum// cost required to reach the n-th floor// space-optimized solution#include <bits/stdc++.h>using namespace std;// function to find the minimum cost// to reach N-th floorint minimumCost(int cost[], int n){ int dp1 = 0, dp2 = 0; // traverse till N-th stair for (int i = 0; i < n; i++) { int dp0 = cost[i] + min(dp1, dp2); // update the last two stairs value dp2 = dp1; dp1 = dp0; } // dp2 gives the cost if started climbing from index 1 // and dp1 from index 0 return min(dp2, dp1);}// Driver Codeint main(){ int a[] = { 2, 5, 3, 1, 7, 3, 4 }; int n = sizeof(a) / sizeof(a[0]); cout << minimumCost(a, n); return 0;} |
Java
// Java program to find the // minimum cost required to // reach the n-th floor // space-optimized solutionimport java.io.*;import java.util.*;class GFG{// function to find // the minimum cost// to reach N-th floorstatic int minimumCost(int cost[], int n){ int dp1 = 0, dp2 = 0; // traverse till N-th stair for (int i = 0; i < n; i++) { int dp0 = cost[i] + Math.min(dp1, dp2); // update the last // two stairs value dp2 = dp1; dp1 = dp0; } return Math.min(dp1, dp2);}// Driver Codepublic static void main(String args[]){ int a[] = { 2, 5, 3, 1, 7, 3, 4 }; int n = a.length; System.out.print(minimumCost(a, n));}} |
Python3
# Python3 program to find # the minimum cost required # to reach the n-th floor# space-optimized solution# function to find the minimum # cost to reach N-th floordef minimumCost(cost, n): dp1 = 0 dp2 = 0 # traverse till N-th stair for i in range(n): dp0 = cost[i] + min(dp1, dp2) # update the last # two stairs value dp2 = dp1 dp1 = dp0 return min(dp1, dp2)# Driver Codeif __name__ == "__main__": a = [ 2, 5, 3, 1, 7, 3, 4 ] n = len(a) print(minimumCost(a, n)) # This code is contributed# by ChitraNayal |
C#
// C# program to find the // minimum cost required to // reach the n-th floor // space-optimized solutionusing System;class GFG{// function to find // the minimum cost// to reach N-th floorstatic int minimumCost(int[] cost, int n){ int dp1 = 0, dp2 = 0; // traverse till N-th stair for (int i = 0; i < n; i++) { int dp0 = cost[i] + Math.Min(dp1, dp2); // update the last // two stairs value dp2 = dp1; dp1 = dp0; } return Math.Min(dp1, dp2);}// Driver Codepublic static void Main(){ int[] a = { 2, 5, 3, 1, 7, 3, 4 }; int n = a.Length; Console.Write(minimumCost(a, n));}}// This code is contributed// by ChitraNayal |
Javascript
<script>// Javascript program to find the// minimum cost required to// reach the n-th floor// space-optimized solution // function to find// the minimum cost// to reach N-th floor function minimumCost(cost,n) { let dp1 = 0, dp2 = 0; // traverse till N-th stair for (let i = 0; i < n; i++) { let dp0 = cost[i] + Math.min(dp1, dp2); // update the last // two stairs value dp2 = dp1; dp1 = dp0; } return Math.min(dp1, dp2); } // Driver Code let a=[2, 5, 3, 1, 7, 3, 4 ]; let n = a.length; document.write(minimumCost(a, n)); // This code is contributed by avanitrachhadiya2155</script> |
PHP
<?php// PHP program to find the // minimum cost required to // reach the n-th floor // space-optimized solution// function to find the minimum // cost to reach N-th floorfunction minimumCost(&$cost, $n){ $dp1 = 0; $dp2 = 0; // traverse till N-th stair for ($i = 0; $i < $n; $i++) { $dp0 = $cost[$i] + min($dp1, $dp2); // update the last // two stairs value $dp2 = $dp1; $dp1 = $dp0; } return min($dp1, $dp2);}// Driver Code$a = array(2, 5, 3, 1, 7, 3, 4);$n = sizeof($a);echo (minimumCost($a, $n));// This code is contributed// by Shivi_Aggarwal?> |
Output
9
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
