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
Recognizing the overlapping subproblems, memoization stores the minimum cost to reach each step once computed, preventing redundant work. The problem reduces to a top-down dynamic programming approach where dp(i) returns the minimum cost to reach step i, computed as the minimum of dp(i-1) + cost[i-1] and dp(i-2) + cost[i-2].
Optimal Approach
Implement a recursive dp function with memoization that returns the minimum cost to reach step i. Base cases return 0 for steps 0 and 1. For other steps, recursively compute dp(i-1) and dp(i-2), add the respective costs, and memoize the minimum. The final answer is dp(len(cost)), representing the minimum cost to reach the top beyond the last step.
Time
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)) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int minCostClimbingStairs(int[] cost) { |
| 6 | Map<Integer, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | java.util.function.IntUnaryOperator dp = new java.util.function.IntUnaryOperator() { |
| 9 | public int applyAsInt(int i) { |
| 10 | if (i <= 1) { |
| 11 | return 0; |
| 12 | } |
| 13 | if (memo.containsKey(i)) { |
| 14 | return memo.get(i); |
| 15 | } |
| 16 | int downOne = cost[i - 1] + applyAsInt(i - 1); |
| 17 | int downTwo = cost[i - 2] + applyAsInt(i - 2); |
| 18 | int res = Math.min(downOne, downTwo); |
| 19 | memo.put(i, res); |
| 20 | return res; |
| 21 | } |
| 22 | }; |
| 23 | |
| 24 | return dp.applyAsInt(cost.length); |
| 25 | } |
| 26 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <algorithm> |
| 4 | #include <functional> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | int minCostClimbingStairs(vector<int>& cost) { |
| 11 | unordered_map<int, int> memo; |
| 12 | |
| 13 | function<int(int)> dp = [&](int i) -> int { |
| 14 | if (i <= 1) { |
| 15 | return 0; |
| 16 | } |
| 17 | if (memo.find(i) != memo.end()) { |
| 18 | return memo[i]; |
| 19 | } |
| 20 | int down_one = cost[i - 1] + dp(i - 1); |
| 21 | int down_two = cost[i - 2] + dp(i - 2); |
| 22 | memo[i] = min(down_one, down_two); |
| 23 | return memo[i]; |
| 24 | }; |
| 25 | |
| 26 | return dp((int)cost.size()); |
| 27 | } |
| 28 | }; |
| 1 | var minCostClimbingStairs = function(cost) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | function dp(i) { |
| 5 | if (i <= 1) { |
| 6 | return 0; |
| 7 | } |
| 8 | if (memo.has(i)) { |
| 9 | return memo.get(i); |
| 10 | } |
| 11 | const downOne = cost[i - 1] + dp(i - 1); |
| 12 | const downTwo = cost[i - 2] + dp(i - 2); |
| 13 | const res = Math.min(downOne, downTwo); |
| 14 | memo.set(i, res); |
| 15 | return res; |
| 16 | } |
| 17 | |
| 18 | return dp(cost.length); |
| 19 | }; |
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
| 5 | def dp(i):
|
| 6 | if i <= 1:
|
| 7 | return 0
|
| 8 | if i in memo:
|
| 9 | return memo[i]
|
| 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]
|
Objective
To define a recursive function dp(i) that returns the minimum cost to reach step i, using memoization to avoid redundant computations.
Key Insight
The recursive function exploits the problem's optimal substructure: the cost to reach step i depends only on the costs to reach steps i-1 and i-2 plus their respective costs. By caching results, the recursion efficiently builds up the solution from base cases.
Interview Quick-Check
Core Logic
The dp function returns 0 for base cases (steps 0 and 1), and for other steps, returns the minimum of dp(i-1) + cost[i-1] and dp(i-2) + cost[i-2], memoizing the result.
State & Boundaries
Base cases dp(0) and dp(1) return 0 because starting at these steps incurs no prior cost.
Common Pitfalls & Bugs
Incorrect base cases or missing memoization checks can cause infinite recursion or exponential time.
Return Minimum Cost to Reach the Top
| 16 | return dp(len(cost)) |
Objective
To compute and return the minimum cost to reach the top of the floor, which is beyond the last step.
Key Insight
Calling dp with the index equal to the length of the cost array represents reaching the top beyond the last step. This triggers the recursive computation of the minimum cost path considering all valid step sequences.
Interview Quick-Check
Core Logic
The final answer is dp(len(cost)), representing the minimum cost to reach the top beyond the last step.
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.
memo = {}Initialize a memoization dictionary to cache computed minimum costs for each step.
This dictionary is essential to store intermediate results, preventing redundant recursive calls and reducing time complexity from exponential to linear.
if i in memo:Return the cached minimum cost for step i if available.
Returning memoized results ensures each subproblem is solved once, guaranteeing linear time complexity.
return dp(len(cost))Return the minimum cost to reach the top of the floor.
Calling dp with len(cost) represents reaching beyond the last step, yielding the final answer to the problem.
down_one = cost[i - 1] + dp(i - 1)Calculate the cost of reaching step i by stepping from i-1.
This represents one possible path to step i, combining the cost of step i-1 with the minimum cost to reach i-1, reflecting the problem's recurrence.
down_two = cost[i - 2] + dp(i - 2)Calculate the cost of reaching step i by stepping from i-2.
This alternative path considers jumping two steps, ensuring all valid sequences are evaluated for minimal cost.
return memo[i]Return the memoized minimum cost for step i.
Returning the computed minimal cost completes the recursive step and propagates the result upward.
def dp(i):Define the recursive function dp that computes the minimum cost to reach step i.
Encapsulating the recursive logic in a helper function allows clean management of the problem's state and memoization.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to linear in this problem?
Because memoization ensures each subproblem dp(i) is computed only once and reused thereafter, eliminating repeated recursive calls that would otherwise cause exponential growth.
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