LeetEye LeetEye
Easy 1D Dynamic Programming ~5 min

Min Cost Climbing Stairs

1d-dp min-cost-climbing-stairs

Problem

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.

Examples

Example 1
Input: cost = [10,15,20]
Output: 15
Start at index 1, pay 15, climb two steps to reach the top.
Example 2
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Key Insight

dp[i] = min cost to reach step i. To reach step i, pay either cost[i-1] from step i-1 or cost[i-2] from step i-2.

dp[i] = min cost to reach step i. dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Answer is dp[n].

How to Approach This Problem

Pattern Recognition: When you see keywords like min cost climbing stairs 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 For cost = [10, 15, 20], the top is:
Answer: Beyond index 2 (index 3)
We need to go PAST the last step. Top is at index n (one beyond array).
2 We pay cost[i] when:
Answer: We leave step i
Pay the cost of the step you're standing on to climb away from it.
3 Minimum cost to reach step i:
Answer: min(dp[i-1], dp[i-2])
Come from i-1 (paying cost[i-1]) or from i-2 (paying cost[i-2]). Take minimum.
4 dp[0] and dp[1] are:
Answer: 0 and 0
We can START at step 0 or 1 for free. We pay when we LEAVE, not arrive.
5 The answer is:
Answer: dp[n]
We want to reach the "top" which is position n (beyond the array).

Solution

def minCostClimbingStairs(cost: List[int]) -> int:
    n = len(cost)
    
    # dp[i] = min cost to reach step i
    # Only need previous two values
    prev2, prev1 = 0, 0
    
    for i in range(2, n + 1):
        curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
        prev2 = prev1
        prev1 = curr
    
    return prev1

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye