Min Cost Climbing Stairs
Problem
Given an integer array cost where cost[i] is the cost of step i, return the minimum cost to reach the top of the floor, where you can start from step 0 or step 1 and move either one or two steps at a time.
- 2 ≤ cost.length ≤ 1000
- 0 ≤ cost[i] ≤ 999
Example
cost = [10, 15, 20]15Starting at step 1 (cost 15) and then climbing two steps reaches the top with total cost 15, which is less than starting at step 0 (cost 10) and climbing steps with total cost 30. The recursion explores both options at each step, memoizing results to avoid repeated calculations. For example, dp(3) computes the minimum cost to reach the top from step 3, which is 0 since the top is beyond the last step. dp(2) computes min(cost[1] + dp(1), cost[0] + dp(0)) = min(15 + 0, 10 + 0) = 10, and so forth, building up the solution.
Approach
Straightforward Solution
A brute-force recursive approach tries all possible paths by exploring one or two steps at a time without caching, leading to exponential time complexity due to repeated calculations.
Core Observation
The minimum cost to reach step i depends only on the minimum costs to reach steps i-1 and i-2 plus the cost of those steps, revealing overlapping subproblems and optimal substructure.
Path to Optimal
PreviewRecognizing the overlapping subproblems, memoization stores the minimum cost to reach each step once computed, preventing redundant work…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewImplement a recursive dp function with memoization that returns the minimum cost to reach step i. Base cases return 0 for steps 0 and 1…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each state dp(i) is computed once and stored in the memo dictionary, resulting in linear time proportional to the number of steps.
Space
O(n)
The memo dictionary stores results for each step, requiring O(n) auxiliary space. The recursion stack depth is also O(n) in the worst case.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem involves making a sequence of decisions with overlapping subproblems and optimal substructure, use a recursive function with memoization to cache intermediate results and avoid redundant computations.
Solution
| 1 | class Solution:
|
| 2 | def minCostClimbingStairs(self, cost: list[int]) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i):
|
| 6 | if i <= 1:
|
| 7 | return 0
|
| 8 | if i in memo:
|
| 9 | return memo[i]
|
| 10 |
|
| 11 | down_one = cost[i - 1] + dp(i - 1)
|
| 12 | down_two = cost[i - 2] + dp(i - 2)
|
| 13 | memo[i] = min(down_one, down_two)
|
| 14 | return memo[i]
|
| 15 |
|
| 16 | return dp(len(cost)) |
Step-by-Step Solution
Initialize Memoization Cache for Subproblem Results
| 3 | memo = {}
|
Objective
To create a dictionary that caches the minimum cost to reach each step, enabling efficient reuse of computed results.
Key Insight
Memoization transforms the naive recursive solution into an efficient dynamic programming approach by storing results of subproblems. This prevents exponential recomputation and ensures each state is solved once.
Interview Quick-Check
Core Logic
The memo dictionary caches dp(i) results, enabling O(1) retrieval and preventing redundant recursive calls.
Common Pitfalls & Bugs
Forgetting to memoize results leads to exponential time complexity due to repeated subproblem evaluations.
Recursively Compute Minimum Cost with Memoization
To define a recursive function dp(i) that returns the minimum cost to reach step i, using memoization to avoid redundant computations.
Return Minimum Cost to Reach the Top
To compute and return the minimum cost to reach the top of the floor, which is beyond the last step.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if i <= 1:Return 0 for base cases where i is 0 or 1.
Starting at step 0 or 1 incurs no prior cost, so the minimum cost to reach these steps is zero, establishing the base cases for recursion.
return 0Check if the result for step i is already memoized.
This lookup prevents redundant computation by returning cached results immediately, a key optimization in memoized recursion.
memo[i] = min(down_one, down_two)Memoize the minimum of the two computed costs for step i.
Storing the minimal cost for step i enables efficient reuse in future recursive calls, embodying the dynamic programming principle.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to linear in this problem?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Min Cost Climbing Stairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Min Cost Climbing Stairs drill