Problem Description

You have a staircase where each step has a cost associated with it, represented by an integer array cost. The value cost[i] represents the cost of stepping on the i-th step.

The rules for climbing the staircase are:

• After paying the cost of a particular step, you can climb either one step or two steps from that position
• You can choose to start your climb from either step 0 or step 1 (you don't need to pay to stand on the starting step)
• The "top" of the floor is considered to be just beyond the last step in the array

Your goal is to find the minimum total cost needed to reach the top of the staircase.

For example, if cost = [10, 15, 20]:

• You could start at step 0, pay 10, climb 2 steps to step 2, pay 20, then climb 1 or 2 steps to reach the top. Total cost: 10 + 20 = 30
• Or you could start at step 1, pay 15, climb 2 steps directly to the top. Total cost: 15
• The minimum cost would be 15

The solution uses dynamic programming with memoization. The function dfs(i) calculates the minimum cost to reach the top starting from step i. Since we can start from either step 0 or step 1, the final answer is the minimum of dfs(0) and dfs(1).

Intuition

The key insight is that at each step, we face a decision: pay the current cost and either climb 1 step or climb 2 steps. This creates a branching decision tree where we want to find the path with minimum total cost.

Think of it backwards - to reach the top from any position i, we must:

1. Pay the cost at position i (which is cost[i])
2. Then make the optimal choice between climbing 1 or 2 steps

This naturally leads to a recursive structure. If we define dfs(i) as "the minimum cost to reach the top starting from step i", then:

• dfs(i) = cost[i] + min(dfs(i+1), dfs(i+2))

The base case occurs when i >= len(cost), meaning we've already reached or passed the top, so no additional cost is needed (return 0).

Why does this work? Because we're breaking down the problem into smaller subproblems. The minimum cost from step i depends only on the minimum costs from steps i+1 and i+2. By solving these smaller problems first (through recursion) and combining their results, we build up to the solution for the original problem.

The memoization (@cache) is crucial here because the same positions will be visited multiple times through different paths. For instance, we might reach step 3 by climbing from step 1 (with a 2-step climb) or from step 2 (with a 1-step climb). Without memoization, we'd recalculate the minimum cost from step 3 multiple times, leading to exponential time complexity.

Since we can start from either step 0 or step 1, we compute both dfs(0) and dfs(1) and take the minimum as our final answer.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a top-down dynamic programming approach using memoization search. Here's how the implementation works:

Core Function Design:

We define a recursive function dfs(i) that calculates the minimum cost to reach the top starting from the i-th step. This function follows the recurrence relation:

• dfs(i) = cost[i] + min(dfs(i + 1), dfs(i + 2))

Base Case:

When i >= len(cost), we've reached or passed the top of the staircase. Since no further climbing is needed, we return 0.

Recursive Case:

For any valid step i:

1. We must pay cost[i] to use this step
2. We then choose the cheaper option between:
   • Climbing 1 step: dfs(i + 1)
   • Climbing 2 steps: dfs(i + 2)
3. Return the sum: cost[i] + min(dfs(i + 1), dfs(i + 2))

Memoization with @cache:

The @cache decorator automatically stores the results of dfs(i) for each unique value of i. When the function is called again with the same parameter, it returns the cached result instead of recalculating. This optimization reduces the time complexity from O(2^n) to O(n).

Finding the Final Answer:

Since we can start from either step 0 or step 1, we compute:

• dfs(0): minimum cost starting from step 0
• dfs(1): minimum cost starting from step 1

The final answer is min(dfs(0), dfs(1)).

Example Walkthrough:

For cost = [10, 15, 20]:

• dfs(3) returns 0 (base case - beyond the top)
• dfs(2) returns 20 + min(dfs(3), dfs(4)) = 20 + min(0, 0) = 20
• dfs(1) returns 15 + min(dfs(2), dfs(3)) = 15 + min(20, 0) = 15
• dfs(0) returns 10 + min(dfs(1), dfs(2)) = 10 + min(15, 20) = 25
• Final answer: min(25, 15) = 15

The memoization ensures each state is computed only once, making the solution efficient with O(n) time and space complexity.

Example Walkthrough

Let's walk through a concrete example with cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1].

We'll trace through the recursive calls to understand how the solution finds the minimum cost.

Step 1: Start the computation We need to find min(dfs(0), dfs(1)).

Step 2: Calculate dfs(0)

• dfs(0) = cost[0] + min(dfs(1), dfs(2))
• dfs(0) = 1 + min(dfs(1), dfs(2))
• We need to compute dfs(1) and dfs(2)

Step 3: Calculate dfs(1)

• dfs(1) = cost[1] + min(dfs(2), dfs(3))
• dfs(1) = 100 + min(dfs(2), dfs(3))
• We need dfs(2) and dfs(3)

Step 4: Build up from the end Let's trace backwards from the base cases:

• dfs(10) = 0 (base case, we're at the top)
• dfs(9) = cost[9] + min(dfs(10), dfs(11)) = 1 + min(0, 0) = 1
• dfs(8) = cost[8] + min(dfs(9), dfs(10)) = 100 + min(1, 0) = 100
• dfs(7) = cost[7] + min(dfs(8), dfs(9)) = 1 + min(100, 1) = 2
• dfs(6) = cost[6] + min(dfs(7), dfs(8)) = 1 + min(2, 100) = 3
• dfs(5) = cost[5] + min(dfs(6), dfs(7)) = 100 + min(3, 2) = 102
• dfs(4) = cost[4] + min(dfs(5), dfs(6)) = 1 + min(102, 3) = 4
• dfs(3) = cost[3] + min(dfs(4), dfs(5)) = 1 + min(4, 102) = 5
• dfs(2) = cost[2] + min(dfs(3), dfs(4)) = 1 + min(5, 4) = 5

Step 5: Complete the calculation Now we can finish calculating dfs(1) and dfs(0):

• dfs(1) = 100 + min(dfs(2), dfs(3)) = 100 + min(5, 5) = 105
• dfs(0) = 1 + min(dfs(1), dfs(2)) = 1 + min(105, 5) = 6

Step 6: Find the minimum starting point

• Starting from step 0: dfs(0) = 6
• Starting from step 1: dfs(1) = 105
• Minimum cost = min(6, 105) = 6

The optimal path: Start at step 0 (pay 1) → jump to step 2 (pay 1) → jump to step 4 (pay 1) → jump to step 6 (pay 1) → jump to step 7 (pay 1) → jump to step 9 (pay 1) → reach the top. Total cost: 6.

Notice how memoization helps here - dfs(2) is needed for both dfs(0) and dfs(1), but it's only calculated once and then cached for reuse.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array cost. This is because the recursive function dfs(i) with memoization (@cache) ensures that each index from 0 to n-1 is computed at most once. Without memoization, it would be O(2^n) due to the overlapping subproblems, but the @cache decorator stores previously computed results, reducing the number of unique function calls to n.

The space complexity is O(n), where n is the length of the array cost. This consists of two components:

1. The recursion call stack depth, which can go up to O(n) in the worst case when we traverse from index 0 to n by taking single steps.
2. The memoization cache, which stores at most n different results (one for each possible index value from 0 to n-1).

Therefore, the overall space complexity is O(n).

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

Common Pitfalls

Pitfall 1: Misunderstanding the Problem's End Condition

The Mistake: Many people incorrectly assume they need to land exactly on the last step (index n-1). This leads to wrong implementations like:

# INCORRECT - assumes we must land on the last step
@cache
def dfs(i):
    if i == len(cost) - 1:  # Wrong base case!
        return cost[i]
    if i >= len(cost):
        return float('inf')  # Penalizing overshooting
    return cost[i] + min(dfs(i + 1), dfs(i + 2))

Why It's Wrong: The problem states the top is "beyond the last step." You can reach the top by either:

• Landing on the last step and taking 1 more step
• Landing on the second-to-last step and taking 2 steps

The Fix: Use the correct base case that returns 0 when you've reached or passed the array bounds:

if i >= len(cost):
    return 0  # Successfully reached the top

Pitfall 2: Forgetting to Consider Both Starting Points

The Mistake: Only considering starting from step 0:

# INCORRECT - only considers starting from step 0
def minCostClimbingStairs(self, cost):
    @cache
    def dfs(i):
        if i >= len(cost):
            return 0
        return cost[i] + min(dfs(i + 1), dfs(i + 2))
  
    return dfs(0)  # Missing dfs(1)!

Why It's Wrong: The problem explicitly allows starting from either step 0 or step 1 without paying their cost initially. You only pay when you step ON a stair to climb from it.

The Fix: Always check both starting positions and take the minimum:

return min(dfs(0), dfs(1))

Pitfall 3: Incorrect Handling of Small Arrays

The Mistake: Not handling edge cases where the array has only 1 or 2 elements:

# Potentially problematic without proper base case
cost = [10]  # Can start at step 0, pay 10, and reach the top
cost = [10, 15]  # Can start at step 1, pay 15, and reach the top

Why It Could Be Wrong: Without the proper base case (if i >= len(cost): return 0), the recursion might not handle these cases correctly.

The Fix: The base case if i >= len(cost): return 0 naturally handles all array sizes:

• For cost = [10]: dfs(0) = 10 + min(dfs(1), dfs(2)) where both dfs(1) and dfs(2) return 0
• For cost = [10, 15]: Works similarly with proper base case handling

Pitfall 4: Not Using Memoization

The Mistake: Implementing the recursive solution without memoization:

# INCORRECT - exponential time complexity without memoization
def dfs(i):
    if i >= len(cost):
        return 0
    return cost[i] + min(dfs(i + 1), dfs(i + 2))

Why It's Wrong: Without memoization, the same subproblems are calculated multiple times, leading to O(2^n) time complexity. For example, dfs(2) might be calculated from both dfs(0) and dfs(1).

The Fix: Always use memoization through either:

• @cache decorator (simplest)
• @lru_cache(None)
• Manual dictionary for storing results

The memoization reduces time complexity from O(2^n) to O(n).