746. Min Cost Climbing Stairs

EasyArrayDynamic Programming
Leetcode Link

Problem Description

The problem presents a scenario where you have a staircase with each step associated with a certain cost given in an integer array called cost. The goal is to figure out the minimum total cost required to reach the top of the staircase. The unique aspect of this problem is that you can choose between taking one step or two steps at a time after paying the corresponding cost. Furthermore, you have the flexibility to start from either the first step (cost[0]) or the second step (cost[1]). The top of the staircase is considered to be one step past the last step, hence you need to decide step by step, which is the cheaper option to achieve the minimum cost to reach the top.

Intuition

The intuition behind the solution comes from dynamic programming concepts, specifically the idea of solving smaller subproblems and building up to the final solution. Since at each step you can make a decision based on the previous two steps, we can work our way up the staircase from bottom to top, calculating the minimum cost needed to reach each step.

The critical observation is that the minimum cost to reach a given step only depends on the minimum costs to reach the two preceding steps. We don't need to remember the path we took, only the costs. This leads us to understand that at each step i, the minimum cost (minCost[i]) is the minimum of the cost of getting to the previous step plus the cost associated with the previous step (minCost[i-1] + cost[i-1]), or the cost of getting to the step before it plus the cost associated with two steps behind (minCost[i-2] + cost[i-2]).

However, to optimize space complexity, we realize that we don't need to keep an array to store all previous minCosts, we can simply use two variables to keep track of these costs as we iterate through the cost array. By repeatedly updating these two variables, we ensure that they always represent the minimum costs to reach the last two steps. At the end of the iteration, the second variable (b in the code) will contain the minimum cost to reach the top of the staircase.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Solution Approach

The solution uses a bottom-up dynamic programming approach where we solve for the smaller subproblems first and use their results to build up to the complete solution. In this scenario, each step has a subproblem that consists of finding the minimum cost to get to that step.

The algorithm uses two variables, a and b, to keep track of the minimum costs up to the two previous steps, respectively. These two variables eliminate the need for an additional auxiliary array that would keep track of the minimum costs for all steps, thus saving space. In algorithmic terms, we reduce the space complexity from O(n) to O(1) by using this approach.

Let's walk through the implementation steps referencing the Python code provided:

  1. We initialize two variables, a and b, both set to 0. These will track the minimum cost to reach the one step behind the current (a) and the current step (b), respectively.
1a = b = 0
  1. We loop through each step in the array from the second step until the end. Since we can either start at step 0 or 1, we don't need to calculate the cost to reach step 0.
1for i in range(1, len(cost)):
  1. Within the loop, we compute the minimum cost to reach the next step, which is determined by the minimum of the cost to get to the current step plus the cost of the current step, and the cost to get to the previous step plus the cost of the previous step.
1a, b = b, min(a + cost[i - 1], b + cost[i])

Here's what happens in the above line:

  • min(a + cost[i - 1], b + cost[i]): This expression finds the minimum cost between taking one step from i-1 or two steps from i-2 to reach the ith step.
  • a, b = b, ...: We then update a to be the previous value of b (since we're moving to the next step, the "current" becomes "previous"), and b is updated to the just-calculated minimum cost.
  1. Lastly, after exiting the loop, variable b holds the minimal cost to reach the top of the staircase. We return b as the solution.
1return b

Note that the top of the floor is one step past the end of the array, and the way the loop is constructed ensures that after iterating through the array, b will represent the cost of getting to the top, not just to the last step.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's walk through an example to illustrate how the solution approach works. Suppose we have the following cost array:

1cost = [10, 15, 20]

The cost array indicates that it costs 10 to move to the first step, 15 to move to the second, and 20 to move to the third. We want to find the minimum cost to reach the top of the staircase, which is one step past the last step (the third step in this case). The top of the staircase is not associated with any cost.

  1. We start by initializing two variables, a and b, to 0. These represent the minimum costs to reach the prior step (a) and the current step (b).
1a = b = 0
  1. Now, we will loop through each step in the array starting from the second step. Since the first step can be chosen as a starting point, we do not need to consider the cost at index 0 at the beginning.
1for i in range(1, len(cost)):

At this point, i = 1.

  1. We compute the minimum cost to the next step.
1a, b = b, min(a + cost[i - 1], b + cost[i])

For i = 1:

  • cost[i-1] is cost[0], which is 10.
  • cost[i] is cost[1], which is 15.
  • a + cost[i - 1] is 0 + 10 = 10.
  • b + cost[i] is 0 + 15 = 15.
  • min(a + cost[i - 1], b + cost[i]) is min(10, 15) which is 10.

Therefore, a becomes 0 and b becomes 10. Now, the minimum cost to reach the second step is 10.

Continue the loop for i = 2.

For i = 2:

  • cost[i-1] is cost[1], which is 15.
  • cost[i] is cost[2], which is 20.
  • a + cost[i - 1] is 0 + 15 = 15.
  • b + cost[i] is 10 + 20 = 30.
  • min(a + cost[i - 1], b + cost[i]) is min(15, 30) which is 15.

Now, a takes the previous value of b, and b takes the new minimum. So, a becomes 10, and b becomes 15.

  1. Since we've reached the end of the array, the b value now represents the minimum cost to reach the top of the staircase. Thus, the minimum cost to get to the top is 15.
1return b

In this example, the cheapest way to reach the top is by starting on the first step with a cost of 10 and then jumping two steps to the top with no additional cost, resulting in a total minimum cost of 10 + 0 = 10. However, due to how the algorithm is structured, b ends up as 15 at the end, which is the correct answer because we are looking for the minimal cost to get to the top, which includes the scenario where we start at the second step (cost[1] = 15) and take one step to the top. The algorithm effectively accounts for both starting points as per the problem requirements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minCostClimbingStairs(self, cost: List[int]) -> int:
5        # Initialize variables to store the minimum cost of reaching the previous two steps.
6        previous_step_cost = current_step_cost = 0
7      
8        # Iterate over the cost array starting from the second element,
9        # since we can start either from step 0 or step 1.
10        for i in range(2, len(cost) + 1):
11            # Compute the minimum cost to reach the current step by taking
12            # a single step from the previous step or a double step from the one before previous.
13            # This compares the cost of reaching the previous step and one step before that,
14            # added to the cost of the step that would be taken.
15            temp = current_step_cost
16            current_step_cost = min(previous_step_cost + cost[i - 2], current_step_cost + (cost[i - 1] if i != len(cost) else 0))
17          
18            # Update the previous step cost for the next iteration
19            previous_step_cost = temp
20      
21        # Return the minimum cost to reach the top of the floor, which is the same as reaching the
22        # end of the cost array, since we can either end at the last step or bypass it.
23        return current_step_cost
24
1class Solution {
2    // Method to calculate the minimum cost to climb stairs
3    public int minCostClimbingStairs(int[] cost) {
4        // Two variables to store the minimum cost to reach the step before the current step (prevStep) 
5        // and the step before the previous step (prevPrevStep).
6        int prevPrevStepCost = 0, prevStepCost = 0;
7    
8        // Looping through the array starting from the second element since the cost of climbing from
9        // the ground (before the first step) to the first or second step is already provided in 'cost' array.
10        for (int i = 2; i <= cost.length; ++i) {
11            // Calculate the minimum cost to reach the current step by comparing the cost of
12            // taking one step from the previous step and the cost of taking two steps from the step before that.
13            int currentStepCost = Math.min(prevStepCost + cost[i - 1], prevPrevStepCost + cost[i - 2]);
14        
15            // Update the costs for the next iteration. The previous step becomes the step before the previous step,
16            // and the current step becomes the previous step.
17            prevPrevStepCost = prevStepCost;
18            prevStepCost = currentStepCost;
19        }
20    
21        // Return the minimum cost to reach the top of the stairs which is either from the last or second-last step.
22        return prevStepCost;
23    }
24}
25
1// The Solution class provides a method to find the minimum cost to reach the top
2// of a staircase, where each step has a certain cost associated with stepping on it.
3class Solution {
4public:
5    // The minCostClimbingStairs function calculates the minimum cost to reach the top
6    // of the staircase given a vector where each element represents the cost of a step.
7    int minCostClimbingStairs(vector<int>& cost) {
8        // Initialize two variables to store the minimum cost to reach the current step
9        // and the previous step.
10        int minCostToCurrent = 0, minCostToPrevious = 0;
11      
12        // Iterate through the steps, starting from the second step (first step is index 0).
13        for (int i = 2; i <= cost.size(); ++i) {
14            // Calculate the minimum cost to reach the current step by comparing:
15            // 1. The cost to reach the previous step (one step behind) and step on current step.
16            // 2. The cost to reach the second previous step (two steps behind) and skip the previous step.
17            int minCostToNext = min(minCostToPrevious + cost[i - 1], minCostToCurrent + cost[i - 2]);
18          
19            // Move the 'current' and 'previous' costs forward for the next iteration.
20            minCostToPrevious = minCostToCurrent;
21            minCostToCurrent = minCostToNext;
22        }
23      
24        // After the loop, minCostToCurrent holds the minimum cost to reach the top of the stairs
25        // since one can step on either the last step or one step before last, so we do not need
26        // to specifically handle the top step.
27        return minCostToCurrent;
28    }
29};
30
1/**
2 * Computes the minimum cost to climb stairs. You can either climb one or two steps at a time.
3 * After you pay the cost, you can either start from the step with index 0, or the step with index 1.
4 *
5 * @param {number[]} cost - The cost of each step.
6 * @return {number} - The minimum cost to reach the top of the floor.
7 */
8function minCostClimbingStairs(cost: number[]): number {
9    // Initialize two variables to store the cumulative cost from two steps back (prevCost) 
10    // and one step back (currentCost), starting at the base, which is zero cost.
11    let prevCost = 0;
12    let currentCost = 0;
13  
14    // Iterate through the array of costs, starting from the second step,
15    // since the first step's cost is already accounted for by the initial costs of 0.
16    for (let i = 2; i <= cost.length; i++) {
17        // Compute the new total cost by taking the minimum of the previous two costs
18        // plus the cost of either taking one step from the previous step or two steps back.
19        let newCost = Math.min(prevCost + cost[i - 2], currentCost + cost[i - 1]);
20      
21        // Update previous and current costs for the next iteration.
22        prevCost = currentCost;
23        currentCost = newCost;
24    }
25  
26    // After iterating through all the steps, the currentCost holds the minimum cost 
27    // to reach the top of the floor.
28    return currentCost;
29}
30
Not Sure What to Study? Take the 2-min Quiz

Which of the following array represent a max heap?

Time and Space Complexity

The given code is a dynamic programming approach to solve the minimum cost climbing stairs problem. Let's analyze the time and space complexity.

Time Complexity:

The time complexity of the code is determined by the loop that iterates over the range 1 to len(cost). Since it goes through each step once, the time complexity is O(n), where n is the number of elements in the cost list.

Space Complexity:

As for the space complexity, the code uses two variables a and b to keep track of the previous two costs only, not needing additional space that is dependent on the input size. Thus, the space complexity is O(1), constant space, as it does not grow with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«