746. Min Cost Climbing Stairs

Reformulated question¶

Given cost[i], the price to step on stair i, and you may move +1 or +2, return the minimum total cost to reach the position just after the last stair; you may start on stair 0 or 1.

Example: cost = [10,15,20] -> 15
- Start at 1, pay 15, jump to top.

Key trick¶

Use DP on the cost to arrive at each step:

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

The answer is not the last step's cost alone:

It is min(dp[n-1], dp[n-2]) because the top is one move after them.

Trap¶

Common mistakes:

Returning dp[n-1] instead of min(dp[n-1], dp[n-2])
Forgetting you can start at step 1
Thinking you must pay for the "top" step
Mutating cost in-place in an interview without saying so

Why is this question interesting?¶

It is a small DP problem where the whole difficulty is defining the state correctly:

cost to stand on a step
not cost to leave it
and the destination is beyond the array

Solve the problem with idiomatic python¶

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        # prev2 = min cost to reach step i-2
        # prev1 = min cost to reach step i-1
        prev2, prev1 = cost[0], cost[1]

        for i in range(2, len(cost)):
            prev2, prev1 = prev1, cost[i] + min(prev2, prev1)

        # Top is reached from either of the last two steps.
        return min(prev2, prev1)

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("cost", "expected"),
    [
        ([10, 15, 20], 15),
        ([1, 100, 1, 1, 1, 100, 1, 1, 100, 1], 6),
        ([1, 2], 1),
        ([0, 0, 0], 0),
        ([5, 5, 5, 5], 10),
        ([1, 2, 3, 4], 4),
        ([0, 2, 2, 1], 2),
    ],
)
def test_min_cost_climbing_stairs(cost, expected):
    assert Solution().minCostClimbingStairs(cost) == expected

Comment my solution¶

Your solution is correct and already interview-good.

Small comments:

n == 1 is unnecessary for this problem because constraints guarantee len(cost) >= 2
Variable names like prev2 and prev1 are a bit clearer than cost_0 and cost_1
Time is \(O(n)\) and space is \(O(1)\), which is optimal

# OK
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        if n == 1:
            return cost[0]
        if n == 2:
            return min(cost[0], cost[1])
        cost_0 = cost[0] # cost up to 0 including
        cost_1 = cost[1] # cost up to 1 including
        for i in range(2, n):
            cost_2 = min(cost_0, cost_1) + cost[i]
            cost_0 = cost_1
            cost_1 = cost_2
        return min(cost_0, cost_1)

Extra¶

While I solved this problem, solving DP problems feels hard and not natural to me. I ask AI for help, specifically about the definition of DP and the intuition about DP problems.

Dynamic programming is just:

solving a big problem by solving smaller overlapping subproblems
storing those answers so you do not recompute them
using a recurrence: "answer for this state = combination of answers of smaller states"

A short mental model:

recursion tells you what depends on what
DP makes it efficient by caching or ordering computations

What DP really is¶

DP appears when:

the problem has many repeated subproblems
the best answer for a larger case can be built from smaller cases
the "future" only needs a small summary of the "past"

That small summary is the state.

Examples:

Fibonacci
- state: n
- recurrence: f(n) = f(n-1) + f(n-2)
Min cost climbing stairs
- state: step i
- recurrence: min cost to reach i depends on i-1 and i-2
House robber
- state: first i houses
- recurrence: rob i or skip i

So DP is not a special bag of tricks.

It is often just:

"At position i, what is the best I can do if I summarize all previous choices by a few values?"

What people usually miss¶

Usually the hard part is not coding.

Usually it is this:

choosing the right state
deciding whether the state means:
- exact answer for index i
- best answer using first i items
- best answer ending at i
- number of ways to reach i
deciding whether the transition is:
- take or skip
- come from left/up/previous
- split at some k
- extend previous answer or restart

Most DP confusion is really state-definition confusion.

What is a state?¶

A state is:

the minimum information needed to continue solving the rest correctly

Good state:

small
complete enough
no unnecessary history

Example: climbing stairs

Bad thought:

"I need the whole path I took"

Good state:

"I only need the minimum cost to arrive at step i"

Why?

because from step i, the past path details do not matter anymore
only the best cost so far matters

That is the core DP skill:

ask: "What from the past still matters?"

When it seems not to be DP, but actually is¶

Many problems are secretly DP when they look like:

1. Greedy at first glance¶

Example:

"At each step pick the cheaper move"

This often fails because local best is not global best.

If choice now changes later options, it may be DP.

Examples:

min cost climbing stairs
coin change
jump game variants
stock trading with cooldown/fees

2. DFS / recursion problems¶

If you naturally write recursive branching like:

try choice A
try choice B
return best

that is often DP waiting for memoization.

Example:

def solve(i):
    return max(solve(i + 1), value[i] + solve(i + 2))

That is already DP logic.

Memoization just stops recomputation.

3. Graph problems¶

A shortest path in a DAG is basically DP.

Why?

nodes are states
edges are transitions
process in dependency order

4. String problems¶

Edit distance, LCS, decode ways feel like string manipulation.

But they are DP because:

state = positions in strings
answer depends on smaller prefixes/suffixes

5. Counting problems¶

Whenever you count ways subject to constraints, it is often DP.

Examples:

number of ways to climb stairs
number of decodings
target sum
partition count

How to recognize DP¶

Look for these clues:

"minimum", "maximum", "count ways", "is it possible"
choices at each step
overlapping recursive calls
constraints too big for brute force, too structured for arbitrary search
problem over:
- index
- prefix
- suffix
- remaining capacity
- position on grid
- subset mask
answer for larger input seems built from nearby/smaller answers

Good trigger question:

"If I solve from some intermediate situation, will I encounter the same intermediate situation again from different paths?"

If yes, likely DP.

How do we solve a DP problem?¶

Use this checklist.

1. Decide what the state means¶

Pick one precise sentence.

Examples:

dp[i] = minimum cost to reach step i
dp[i] = maximum money from first i houses
dp[i][j] = LCS length using first i chars of a and first j chars of b

If you cannot say this in one clean sentence, your state is probably not ready.

2. Write the recurrence in words first¶

Before formulas, say:

"To get to step i, I must come from i-1 or i-2"
"At house i, I either rob it or skip it"
"For two prefixes, if chars match I extend; otherwise I drop one side"

If words are clear, formula follows naturally.

3. Define base cases¶

Ask:

smallest state?
empty input?
first row/first column?
what is trivially true?

This is where many bugs happen.

4. Pick top-down or bottom-up¶

Top-down:

write recursive recurrence
add memo
best when recurrence is easy but table order is annoying

Bottom-up:

fill table iteratively
best when dependencies are simple
often easier to optimize space

5. Optimize space if possible¶

If dp[i] depends only on a few previous states:

keep only those values

Like stairs:

prev2, prev1 = ...

instead of whole array.

The real intuition for finding recurrence¶

Think backwards.

Instead of asking:

"How do I build the whole answer?"

ask:

"What is the last decision?"
"Where could I have come from?"
"If I knew the best answer for smaller states, how would I use it?"

This often unlocks DP immediately.

Examples.

Min cost climbing stairs¶

Ask:

to stand on step i, where could I come from?

Answer:

i-1 or i-2

So:

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

House robber¶

Ask:

for first i houses, what happened with house i?

Answer:

either skip it
or rob it, forcing skip of i-1

So:

best up to i = max(skip, rob)

Coin change¶

Ask:

to make amount a, what could the last coin be?

Answer:

any coin c

So:

dp[a] = 1 + min(dp[a-c])

That "last move" trick is one of the most useful DP habits.

A practical way to train state formulation¶

When you see a problem, try these templates.

Template A: prefix DP¶

dp[i] = answer using first i items

Common for:

arrays
strings
house robber
partition problems

Template B: ending-at DP¶

dp[i] = best answer ending exactly at i

Common for:

LIS
max subarray
path ending at a cell

Template C: position/state machine DP¶

dp[i][state] = answer at time/index i while being in some mode

Common for:

stock trading
holding/not holding
cooldown
parity
previous choice matters

Template D: grid DP¶

dp[r][c] = answer to reach or compute at cell (r, c)

Template E: interval DP¶

dp[l][r] = answer for subarray/string from l to r

Common for:

palindrome
matrix chain
burst balloons

Template F: knapsack DP¶

dp[i][cap] = answer using first i items with capacity cap

Common for:

take/skip with constraints

If a problem feels vague, try forcing it into one of these patterns.

Why DP problems matter¶

Because they teach a very general skill:

compressing history into the smallest sufficient summary

That idea appears everywhere:

algorithm design
optimization
shortest paths
machine learning state models
systems with decisions over time

In interviews, DP matters because it tests whether you can:

model a problem
define precise states
reason from dependencies
avoid brute force

It is less about memorizing formulas and more about structured thinking.

Why DP feels hard at first¶

Because it asks you to invent an abstraction.

Brute force feels natural:

try everything

DP asks:

what information is enough so I don't need to try everything again?

That is a more mathematical habit.

So if DP feels slippery, that is normal.

You are not failing at coding.

You are training the skill of state compression.

Top-down vs bottom-up intuition¶

Top-down:

easiest to discover
write the brute force recursive idea first
then memoize repeated calls

Bottom-up:

easiest to optimize and reason about iteration order
compute smallest states first

A good learning strategy:

first derive recurrence recursively
then convert to bottom-up

That separates:

finding the idea
implementing efficiently

A useful process on every DP problem¶

Use this exact sequence:

Define the subproblem.
- "What does dp[...] mean?"
Ask how the final answer relates to smaller subproblems.
- "What was the last move?"
Write the recurrence.
Write base cases.
Decide computation order.
Check whether memory can be compressed.

If stuck, ask these rescue questions:

What are the choices at each step?
Which past details matter for future decisions?
Can I describe the problem using prefixes/suffixes/subarrays?
What is the last action in an optimal solution?
If I write brute force recursion, what parameters define a unique subproblem?

That last one is very powerful:

the recursive function arguments often are the DP state

Example: your stairs problem, slowly¶

Suppose:

cost = [10, 15, 20]

State:

dp[i] = min cost to stand on step i

Then:

dp[0] = 10
dp[1] = 15

For step 2:

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

Now top is beyond the array.

To reach top:

come from step 1 or 2

So answer:

min(dp[1], dp[2]) = min(15, 30) = 15

The subtle point is:

top is not a paid step
that is why answer is min(last two) and not dp[-1]

This is exactly the kind of state-definition detail that makes or breaks DP.

The most common DP mistake¶

People often choose a state that is almost right.

Examples:

"min cost after leaving step i"
"best answer somewhere near i"
"number of ways until here maybe including this maybe not"

That vagueness kills the recurrence.

Fix:

make state meaning brutally precise

Example:

bad: dp[i] = min cost around step i
good: dp[i] = min cost to stand on step i

Once precise, transitions become obvious.

A good learning progression¶

Practice in this order:

Fibonacci / climbing stairs
Min cost climbing stairs
House robber
Coin change
Maximum subarray
Unique paths
Decode ways
Longest increasing subsequence
Longest common subsequence
Knapsack

While practicing, force yourself to write for each problem:

state
recurrence
base case
answer location

Just those four lines.

That builds the instinct.

The shortest summary¶

DP is:

solve repeated subproblems once
using a state that captures all relevant past information
and a recurrence that connects that state to smaller states

If you want DP to click, focus less on "this is a DP problem" and more on:

what is the smallest state that fully describes progress?

That one question is the heart of DP.