Domain 1EasyCORE

Min Cost Climbing Stairs

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Dynamic Programming

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 cost where cost[i] represents the cost of stepping on the i-th step.

Outputs:

  • An integer representing the minimum cost to reach the top of the staircase.

Implicit Constraints/Edge Cases:

  • The length of the cost array is between 2 and 1000.
  • Each element in the cost array 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:

  1. Initialize two variables, prev1 and prev2, to 0. These will store the minimum costs to reach the previous two steps.
  2. Iterate through each step in the cost array:
    • Calculate the current cost as the minimum of prev1 + cost[i] and prev2 + cost[i-1].
    • Update prev2 to be prev1, and prev1 to be the current cost.
  3. After iterating through all steps, return the minimum of prev1 and prev2.

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 cost is 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.