Return the minimum cost to reach the top of the floor by climbing the stairs either 1 or 2 steps at a time.
LeetCode-746: You are given an integer array cost where cost[i]
is the cost of $i^{th}$ step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0
, or the step with index 1
. Return the minimum cost to reach the top of the floor.
To minimize the cost for $i^{th}$ step, we can either come from the $i-1^{th}$ step or the $i-2^{nd}$ step; i.e. choose the minimum of the two. We can define a recurrence relation for the problem as follows:
The above mentioned recurrence relation can be solved using dynamic programming. We can define an array of size n+1
where n
is the length of the cost
array.
The minCost[i]
will store the minimum cost to reach the $i^{th}$ step. The base cases are:
minCost[0] = cost[0]
minCost[1] = cost[1]
Here is a java implementation of the above approach:
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] minCost = new int[n];
minCost[0] = cost[0];
minCost[1] = cost[1];
for(int i=2; i < n ; i++){
minCost[i] = cost[i] + Math.min(minCost[i-1], minCost[i-2]);
}
return Math.min(minCost[n-1], minCost[n-2]);
}
The time complexity for the above approach is $O(n)$ where $n$ is the length of the cost
array. The space complexity is also $O(n)$ as we are using an array of size n
to store the minimum cost to reach the $i^{th}$ step.
Be notified of new posts. Subscribe to the RSS feed.