Introduction

The Min Cost Climbing Stairs problem introduces cost optimization in Dynamic Programming.

You are given:

cost[i]

where:

cost[i]represents the cost of stepping on stair i.

At every move, you can climb:

1 stair or 2 stairs

Goal:

Reach the top with minimum cost.

Example

cost = [10,15,20]

Output = 15

Explanation:

Start from stair 1Cost = 15
Jump directly to top
Answer = 15

Constraints

 2 <= cost.length <= 1000

Key Observation

To reach stair:

 i

you can come from:

i - 1 or i - 2

Therefore:

dp[i] = cost[i] + min(dp[i-1], dp[i-2])

This forms the DP recurrence.

Approach 1 : Memoization

Explanation

Store already calculated answers.

Steps:

  1. Solve recursively.
  2. Save results.
  3. Reuse computed values.
  4. Avoid repeated work.

Approach 2 : Tabulation

Explanation

Build answers from smaller states.

Base Cases:

dp[0] = cost[0]dp[1] = cost[1]

Transition:

dp[i] = cost[i] + min(dp[i-1],dp[i-2])

Final Answer:

 min(dp[n-1], dp[n-2)

because the top itself has no cost.

Dry Run

Input:

cost = [10,15,20]

DP Table:

dp[0] = 10dp[1] = 15
dp[2] = 20 + min(15,10) = 30

Answer:

min(30,15) = 15

Approach 3 : Space Optimized DP

Explanation

Only previous two values are required.

Instead of storing an entire array:

prev2prev1

Maintain two variables.

This reduces:

Space Complexity to O(1)

Practice

Memoization

Time Complexity: O(n)
Space Complexity:O(n)
Tabulation
Time Complexity: O(n)
Space Complexity: O(n)
Space Optimized DP
Time Complexity:O(n)
Space Complexity:O(1)

Why This Problem is Important

This problem teaches:

  • Cost Optimization
  • Dynamic Programming
  • State Transitions
  • Bottom-Up DP
  • Space Optimization

Real-World Applications

Used in:

  • Route Optimization
  • Resource Allocation
  • Budget Planning
  • Navigation Systems
  • Cost Minimization Problems

Common Beginner Mistakes

  • Using maximum instead of minimum
  • Wrong base cases
  • Returning dp[n-1]
  • Forgetting top stair has no cost
  • Incorrect recurrence

Interview Tip

Interviewers expect:

 Recursion→ Memoization
→ Tabulation
→ Space Optimization

Always explain:

  • state definition
  • recurrence relation
  • why answer is min(dp[n-1], dp[n-2])

Related Questions

  • Fibonacci
  • Climbing Stairs
  • House Robber
  • Coin Change
  • Decode Ways

Final Takeaway

Min Cost Climbing Stairs is the first Dynamic Programming problem focused on optimization rather than counting.

It teaches:

  • how to define DP states
  • how to minimize cost
  • how to build recurrence relations
  • how to optimize memory

Mastering this problem prepares you for more advanced optimization-based DP questions.