Minimum Cost Climbing Stairs

Problem Statement

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.

Approach

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:

1. minCost[0] = cost[0]
2. minCost[1] = cost[1]

Implementation

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]);
    }

    // since both the last and second-to-last steps 
    // can be the used to reach the top, the final 
    // minimum cost is the lesser of the two
    return Math.min(minCost[n-1], minCost[n-2]);
}

Complexity Analysis

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.

Follow-up

Can we optimize the space complexity of the above approach?

The above mentioned approach uses an array of size n to store the minimum cost to reach the $i^{th}$ step. But as we can see, we only need the minimum cost for the $i-1^{th}$ and $i-2^{nd}$ step to calculate the minimum cost for the $i^{th}$ step.

So, we can optimize the space complexity by using two variables to store the minimum cost for the $i-1^{th}$ and $i-2^{nd}$ step.

Here is an optimized implementation of the above approach:

public int minCostClimbingStairs(int[] cost) {
    int costSecondLastStep = cost[0];
    int costLastStep = cost[1];

    for(int i=2; i < cost.length; i++){
        int costCurrentStep = cost[i]+Math.min(costSecondLastStep,costLastStep);
        costSecondLastStep = costLastStep;
        costLastStep = costCurrentStep; 
    }
    
    // since both the last and second-to-last steps 
    // can be the used to reach the top, the final 
    // minimum cost is the lesser of the two
    return Math.min(costSecondLastStep, costLastStep);
}