Min Cost Climbing Stairs Problem in Java
In this tutorial, we are going to learn about the Min Cost Climbing Stairs Problem. The cost of the i th step on a staircase is represented by the integer array cost[] of length N. We have the option of climbing one or two stairs when the cost that is paid. We can begin at step 0 or step 1, depending on our preference. To get to the top of the floor, return the minimal cost. Let's see a few examples to understand it. In the input, the number N will be given to us, as well as the cost[] for each stair to step.
Example 1:
Input:
N = 3
Cost[]= { 30, 35, 40}
Output: 35
Explanation: Cheapest choice is to begin at index 1. Pay the cost 35 and climb the stairs to reach the top.
Example 2:
Input:
N = 5
Cost[]= { 1, 5, 2, 3, 1}
Output: 4
Explanation: the cheapest choice is to begin at index 1. Pay 1 and climb 2 stairs to reach index 3, then pay 3 and climb 2 stairs to reach the top at index 5. The total cost is 4.
Approach: Using Recursion
In this Approach, we use recursion to find min cost of climbing stairs. We use a recursive function called minCostsClimbStair, which takes an array of costToClimb for each stair and a helper function to calculate the minimum cost to reach a specific stair. We consider the base case when n is less than or equal to 1 and then recursion for memoization to avoid redundant calculations. We Store min cost to reach each stair in an array called minCostsArr, by initializing with a length of costToClimb.length + 1. Then, we iterate over the stairs starting from index 2, calculating the min cost at each step using the helper function, and return the cost at index n.
Let's see how one can implement the above-mentioned problem's solution.
FileName: FindMinCostToClimbStair .java
public class FindMinCostToClimbStair {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// Calculate the minimum cost
int minCost = Math.min(helper(cost, n - 1), helper(cost, n - 2));
return minCost;
}
// Helper method for recursion
public int helper(int[] cost, int n) {
if (n <= 1)
return cost[n];
// Recursive calculation to find min cost
int ans = Math.min(helper(cost, n - 1), helper(cost, n - 2)) + cost[n];
return ans;
}
public static void main(String[] args) {
FindMinCostToClimbStair g = new FindMinCostToClimbStair();
// provide costs as input
int[] cost = {30, 35, 40};
System.out.println("Min cost for climbing is: " + g.minCostClimbingStairs(cost));
}
}
Output:
Min cost for climbing is: 35
Complexity Analysis: The program uses recursion with memorization. Therefore the time complexity and space complexity is O(N), where N is number of stairs.
Approach: Using Dynamic Programming
In this Approach, we use dynamic programming, specifically memoization, to calculate the min cost to travel each stair. First, we will create an array called minCostsArr, and starts from index 2. Then we iterate all the stairs, calculating the min cost at each step i. For climbing the i th stair, the least expensive alternative is to pay the charge at the (i-2) stair and add the cost of climbing from there or to pay the charge at the (i-1) stair and add the cost of climbing from there. After loading the minCostsArr array, the lowest cost for getting to the top of the stairs is denoted by the minimal cost saved at index costToClimb.length.
Let's see how one can implement the above-mentioned problem's solution.
FileName: FindMinCostToClimbStair .java
public class FindMinCostToClimbStair {
public int minCostsClimbStair(int[] costToClimb) {
int[] minCostsArr = new int[costToClimb.length + 1];
for(int i = 2; i <= costToClimb.length; ++i ) {
minCostsArr[i] = Math.min(minCostsArr[i - 2] + costToClimb[i - 2], minCostsArr[i - 1] + costToClimb[i - 1]);
}
return minCostsArr[costToClimb.length];
}
public static void main(String[] args) {
FindMinCostToClimbStair g = new FindMinCostToClimbStair();
// Provide costs
int[] cost = {5, 10, 15, 20, 25, 30};
System.out.println("Minimum cost for Climbing: " + g.minCostsClimbStair(cost));
}
}
Output :
Minimum cost for Climbing: 45
Complexity Analysis: The program uses a single loop to iterate over a cost array, to find the minimum cost based on earlier steps. The time complexity is O(n), where n is the total number of steps. The space complexity is also O(N), where n is the input array cost because program uses an array minCostsArr with a length of n + 1 to store the minimum cost for every step.