Skip to content

Volume ITechnology

4.23.2 — Min Cost Climbing Stairs ​

LeetCode 746 · Easy

The problem ​

cost[i] is what you pay to step off stair i. From a stair you may move one or two stairs up. You may start at index 0 or index 1, and you must reach the top — one past the last stair. Return the minimum total cost.

cost = [10,15,20]           →  15    (start at 1, pay 15, jump 2 to the top)
cost = [1,100,1,1,1,100,1,1,100,1]   →  6

The pattern ​

Identical to 4.23.1 Climbing Stairs with one operator changed. Counting used +; optimising uses min.

Let dp[i] be the cheapest way to reach stair i. You arrive from i − 1 or from i − 2, and reaching either of those already cost something, plus the price of stepping off it:

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

Read it in words: the cheapest way here is the cheaper of arriving from one below or two below, in each case paying that stair's exit price.

dp[0] = dp[1] = 0, because starting at either is free.

The answer is dp[n], not dp[n-1] — the top is one past the last stair. That off-by-one is the whole trap in this problem.

The definition that decides everything ​

There are two ways to define the state and they lead to different-looking code:

  • dp[i] = cheapest cost to reach stair i (used here). You pay when you leave.
  • dp[i] = cheapest cost to reach the top starting from stair i. Then dp[i] = cost[i] + min(dp[i+1], dp[i+2]), the loop runs backwards, and the answer is min(dp[0], dp[1]).

Both are correct. Pick one, say it out loud, and stay consistent. Mixing the two mid-solution is where the off-by-one errors come from, and it is far more common than getting the recurrence wrong.

The solution ​

python
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        prev, curr = 0, 0                    # (1) dp[0], dp[1] — both free to start

        for i in range(2, len(cost) + 1):  # (2)
            prev, curr = curr, min(curr + cost[i - 1], prev + cost[i - 2])  # (3)

        return curr                          # (4) dp[n], the top
ts
function minCostClimbingStairs(cost: number[]): number {
  let prev = 0, curr = 0;  // (1)

  for (let i = 2; i <= cost.length; i++) {  // (2)
    [prev, curr] = [curr, Math.min(curr + cost[i - 1], prev + cost[i - 2])];  // (3)
  }

  return curr;  // (4)
}

Line by line ​

Here dp[i] means "the cheapest cost to stand on stair i". You pay a stair's cost when you step off it. The top is one past the last stair, at index n.

(1) Standing on stair 0 or stair 1 costs nothing, because you may start on either. So dp[0] = dp[1] = 0. prev and curr hold dp[i-2] and dp[i-1].

(2) Work out each stair from 2 up to the top, n.

(3) You reach stair i either from stair i − 1, paying its cost, or from stair i − 2, paying its cost. Take the cheaper:

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

Read it as "the cheaper of: the cost to stand one below plus that stair's cost, or the cost to stand two below plus that stair's cost". Then slide prev and curr up by one.

(4) curr now holds dp[n], the cheapest way to reach the top.

The loop runs to len(cost) inclusive, because the top is index n and that is the value you want.

prev and curr hold dp[i-2] and dp[i-1] at the top of each iteration. Only two cells are ever read, so no array is needed — form 4 from 4.22.

The simultaneous assignment keeps prev available while curr is being recomputed.

If the two variables feel error-prone, write the array version first and collapse it afterwards:

python
dp = [0] * (len(cost) + 1)
for i in range(2, len(cost) + 1):
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[-1]

Identical, easier to check, O(n) space. In an interview, write this one and then offer the O(1) version.

Trace ​

cost = [10, 15, 20]

ifrom i−1from i−2dp[i]
2dp[1] + cost[1] = 0 + 15 = 15dp[0] + cost[0] = 0 + 10 = 1010
3dp[2] + cost[2] = 10 + 20 = 30dp[1] + cost[1] = 0 + 15 = 1515

Answer 15, matching the expected output. Note that stair 2 is cheapest to reach at 10, but the best route to the top skips it entirely.

Edge cases ​

  • Two stairs. Start on the cheaper one and step straight to the top. The answer is the smaller cost.
  • All costs zero. The answer is 0.
  • The cheapest plan skips a cheap stair, like [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]. The recurrence still finds it, because it tries both moves at every stair.

Complexity ​

O(n) time, O(1) space.

Where this goes next ​

  • Climbing Stairs — the counting version. min becomes +. 4.23.1.
  • House Robber — the same two-variable rolling shape, with the twist that choosing a value forbids the neighbouring one. 4.23.3.
  • Minimum Path Sum, Triangle — the same idea in two dimensions.

The operator table is worth memorising, because it is the only thing that changes between a large family of problems:

the question asksthe operator
how many ways+
cheapest / fewestmin
best / largestmax
is it possibleor

Same recurrence shape, four different questions.

What the interviewer will push on ​

"What does dp[i] mean?" Say it in words before writing anything. This is the question, and vague answers here produce the off-by-one.

"Why does the loop go to n and not n − 1?" The top is one past the last stair.

"Can you define the state the other way round?" Yes — cost from i to the top, running backwards. Both work.

"O(1) space?" Two variables.

"What if you could climb up to k stairs?" Minimise over the previous k cells. A monotonic deque keeps it O(n) instead of O(nk) — the structure from 4.6.6.

One thing to volunteer: state the state definition and the base cases before the recurrence. Most wrong DP answers have the right recurrence and the wrong base or boundary.

Next: 4.23.3 House Robber — the first problem where a choice now removes an option later, which is the sign that greedy will fail.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet