Problem 29 - Min Cost Climbing Stairs

Explore our archive for previous posts.

Question

You are given an integer array cost where cost[i] is the cost of ith 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.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000

• 0 <= cost[i] <= 999

Approach

This problem is an extension to the Climbing Stairs problem

discussed in a previous edition of the newsletter. Please check that problem out before proceeding with understanding this problem.

This solution's approach is based on dynamic programming. The goal is to find the minimum cost to climb to the top of a staircase, where each step has a cost associated with it.

The algorithm initializes a dynamic programming array dp of size cost.length + 1 to store the minimum cost to reach each step. It starts by setting up base cases: dp[0] = 0 and dp[1] = 0, as the minimum cost to reach the first and second steps is zero (there is no cost to start from these steps).

Then, it iterates through the rest of the array. To reach the current step 'i', a person can either come from step 'i-1' (taking one step) or from step 'i-2' (taking two steps). The algorithm chooses the cheaper option between the two, ensuring that the person takes the path with the minimum cost. Finally, the minimum cost to reach the top is stored in dp[cost.length].

Solution

Solve it here

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        
        // Calculate the minimum cost to reach each step from 2 to cost.length
        for (int i = 2; i <= cost.length; i++) {
            // To reach step 'i', the person can either come from 
            // a. step 'i-1' (taking one step), or 
            // b. step 'i-2' (taking two steps).
            // We choose the cheaper option between the two.
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        
        // Return the minimum cost to reach the top
        return dp[cost.length];
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(n), where 'n' is the number of steps (the length of the cost array). The algorithm iterates through the cost array once, performing constant-time operations at each step.

Space Complexity: The space complexity is O(n) as we use a dynamic programming array dp of size cost.length + 1 to store the results for each step. The size of the array grows linearly with the number of steps, so the space complexity is proportional to 'n'.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!