Log inSign up
easyLeetCodeNot Started

Min Cost Climbing Stairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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 (index n).

### Example 1 - Input: cost = [10, 15, 20] - Output: 15 - Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. - Total cost is 15.

### Example 2 - Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] - Output: 6 - Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. - Total cost is 6.

Constraints:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model 1D linear decision problems with two preceding dependencies.
  • Handle multi-choice base conditions (start at index 0 or 1).
  • Optimize memory consumption from O(n) to O(1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • 1D sequential step decisions (step 1 or step 2).
  • Additive cost minimization.
  • Reaching index n from index 0 or 1.

Algorithmic Decision Tree:

  • Transitions involve only step i - 1 and step i - 2.

Connected Patterns:

Climbing StairsHouse RobberFibonacci Number

1. Recursive Branching

Intuition

Recursively try taking 1 step or 2 steps from step 0 and step 1, calculating total cost.

Algorithm

  1. Define solve(i): min cost to reach top from step i.
  2. If i >= n, return 0.
  3. Return cost[i] + min(solve(i + 1), solve(i + 2)).
  4. Overall answer is min(solve(0), solve(1)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int i, const vector<int>& cost) {
9 if (i >= cost.size()) return 0;
10 return cost[i] + min(solve(i + 1, cost), solve(i + 2, cost));
11 }
12public:
13 int minCostClimbingStairs(vector<int>& cost) {
14 return min(solve(0, cost), solve(1, cost));
15 }
16};
17
18int main() {
19 Solution sol;
20 vector<int> cost = {10, 15, 20};
21 cout << "Min Cost: " << sol.minCostClimbingStairs(cost) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. 1D Tabulation Array (O(n) Space)

Intuition

Build a dp array where dp[i] is the minimum cost to reach step i.

Algorithm

  1. Initialize dp array of size n + 1 with 0.
  2. dp[0] = 0, dp[1] = 0 (starting steps have 0 cost to reach).
  3. For i from 2 to n:
  4. dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]).
  5. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minCostClimbingStairs(vector<int>& cost) {
10 int n = cost.size();
11 vector<int> dp(n + 1, 0);
12 for (int i = 2; i <= n; ++i) {
13 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
14 }
15 return dp[n];
16 }
17};
18
19int main() {
20 Solution sol;
21 vector<int> cost = {10, 15, 20};
22 cout << "Min Cost: " << sol.minCostClimbingStairs(cost) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

3. Space-Optimized O(1) Variables

Intuition

Maintain two scalar variables representing the minimum costs to reach the preceding two steps.

Algorithm

  1. Initialize prev2 = 0 (cost to reach step 0) and prev1 = 0 (cost to reach step 1).
  2. Loop i from 2 to n:
  3. curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]).
  4. prev2 = prev1.
  5. prev1 = curr.
  6. Return prev1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minCostClimbingStairs(vector<int>& cost) {
10 int prev2 = 0, prev1 = 0;
11 for (int i = 2; i <= cost.size(); ++i) {
12 int curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
13 prev2 = prev1;
14 prev1 = curr;
15 }
16 return prev1;
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<int> cost = {10, 15, 20};
23 cout << "Min Cost: " << sol.minCostClimbingStairs(cost) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(2^n)O(n)Exhaustive branching over 1-step or 2-step options.Overlapping subproblems
2.1D Array DPO(n)O(n)Iteratively fill dp array from index 2 to n.Array allocation
3.Space-Optimized O(1) VariablesOptimalO(n)O(1)Track only the last two step values using two scalars.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Stopping at index n - 1 instead of index n (the top is beyond the last step).

Pitfall 2:

Adding cost[i] before stepping onto step i rather than when stepping off it.

Crucial Edge Cases to Validate:

  • n = 2: Minimum cost is simply min(cost[0], cost[1]).
  • All cost elements equal 0: Total cost is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out that this is an exact cost-weighted analog of Climbing Stairs (Fibonacci numbers).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the base cost to reach step 0 and step 1 initialized to 0?

Back to DSA Sheet