746. Min Cost Climbing Stairs
Model: qwen2.5-coder:14b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 51.0%
Problem Breakdown
The problem requires finding the minimum cost to reach the top of a staircase where each step has an associated cost. You can start from either step 0 or step 1 and move up by taking one or two steps at a time. The goal is to minimize the total cost incurred while reaching the top.
Inputs:
- An integer array
costwherecost[i]represents the cost of stepping on thei-thstep.
Outputs:
- An integer representing the minimum cost to reach the top of the staircase.
Implicit Constraints/Edge Cases:
- The length of the
costarray is between 2 and 1000. - Each element in the
costarray is a non-negative integer (0 <= cost[i] <= 999). - There are no negative costs, so we don’t need to handle underflow or negative numbers.
Intuition
A brute-force approach would involve exploring all possible paths from either step 0 or step 1 to the top of the staircase. This would result in an exponential time complexity due to the branching factor of two (one or two steps at a time).
To optimize this, we can use dynamic programming to store the minimum cost to reach each step. The key insight is that the minimum cost to reach step i depends only on the minimum costs to reach the previous two steps (i-1 and i-2). This allows us to build up the solution iteratively from the bottom.
Approach
We will use an iterative dynamic programming approach with constant space complexity. The idea is to maintain two variables, prev1 and prev2, which store the minimum costs to reach the previous two steps. At each step, we calculate the current cost as the minimum of the costs to reach the previous two steps plus the cost of the current step. We then update prev1 and prev2 accordingly.
Steps:
- Initialize two variables,
prev1andprev2, to 0. These will store the minimum costs to reach the previous two steps. - Iterate through each step in the
costarray:- Calculate the current cost as the minimum of
prev1 + cost[i]andprev2 + cost[i-1]. - Update
prev2to beprev1, andprev1to be the current cost.
- Calculate the current cost as the minimum of
- After iterating through all steps, return the minimum of
prev1andprev2.
Complexity Analysis
Time Complexity: O(n), where n is the length of the cost array. We iterate through the array once.
Space Complexity: O(1). We use only a constant amount of extra space for variables.
Solution
def minCostClimbingStairs(cost):
prev1, prev2 = 0, 0
for i in range(len(cost)):
current_cost = min(prev1 + cost[i], prev2 + (cost[i-1] if i > 0 else 0))
prev2 = prev1
prev1 = current_cost
return min(prev1, prev2)
Edge Cases Handled
- Minimum Length: The problem guarantees that the length of
costis at least 2, so we don’t need to handle cases where it’s less than 2. - All Zero Costs: If all costs are zero, the minimum cost will be zero, as no steps incur any cost.
- Uniform Costs: If all costs are uniform (e.g., all 1s), the solution will correctly compute the minimum cost based on the number of steps taken.