min-cost-climbing-stairs

Difficulty: Easy  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/min-cost-climbing-stairs/start

The story

A pharmaceutical lab is running a stability study where each step of a long analytical procedure consumes reagent. The protocol allows two stride lengths at every checkpoint: do one step (cheap, slow) or skip ahead by two steps (faster, but the bypass step still bills the reagent of the stair you launched from). The scientist starts at the lab bench, picks either of the first two steps as the entry, and reports the total reagent bill to finance.

That bookkeeping is min-cost-climbing-stairs. Once you see it framed this way, the same recurrence appears wherever a sequence of decisions has only a couple of look-back options and you want the cheapest path: print-job scheduling on industrial presses, billing micro-segments on Stripe invoice runs, click-stream tax minimisation across a checkout flow.

What's actually being asked

You are given a cost array of length n. cost[i] is the price you pay to step on stair i. From stair i you may advance by one or two. You may start at index 0 or index 1 for free; the entry is on the house. The "top" is index n, one past the last stair, and you do not pay to arrive there.

Return the minimum total cost to reach index n.

Examples:

• cost = [10, 15] → 10. Start on the cheaper stair, step off the top.
• cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] → 6. Start at index 0 (cost 1) and weave around the 100s.

The naive approach

Recurse on every choice:

def best(i, cost):
    if i >= len(cost): return 0
    return cost[i] + min(best(i+1, cost), best(i+2, cost))

Then return min(best(0, cost), best(1, cost)). Correct, but the call tree is exponential. For n = 30 it already costs ~10⁹ calls. For n = 100000 the universe runs out.

The key insight

To arrive at index i, the only legal predecessors are i-1 (taking a one-step) or i-2 (taking a two-step). You paid cost[i-1] or cost[i-2] respectively to be on that predecessor stair, plus whatever it cost to reach it. So:

# Recurrence:
# dp[i] = cost paid by the moment you arrive at index i
# dp[0] = dp[1] = 0   (free starts)
# dp[i] = min( dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2] )   for i >= 2
# Answer = dp[n]

The four DP questions:

1. State: dp[i] is the minimum cost paid to arrive at index i (you have not yet paid cost[i]).
2. Base case: dp[0] = 0, dp[1] = 0 because entry is free.
3. Transition: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
4. Answer: dp[n], where n is the length of the cost array.

Step-by-step approach

Bottom-up, O(n) time, O(n) space:

def min_cost(cost):
    n = len(cost)
    if n <= 1:
        return 0
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    return dp[n]

Only the previous two values are ever read. Collapse to two scalars:

def min_cost(cost):
    n = len(cost)
    if n <= 1:
        return 0
    a, b = 0, 0
    for i in range(2, n + 1):
        a, b = b, min(b + cost[i-1], a + cost[i-2])
    return b

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

Worked example

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1], n = 10

Return 6. Verified.

Complexity

• Time: O(n).
• Space: O(1) for the rolling pair, O(n) for the array form.

Common pitfalls

• Treating cost[i] as the price of leaving the stair: you double-count or misalign. The price is paid for being on stair i, full stop.
• Off-by-one between stair index and dp index: the top is dp[n], not dp[n-1]. The last cost in the array is cost[n-1]; you can step off it to reach n.
• Starting cost included by accident: dp[0] and dp[1] are both zero. If you write dp[0] = cost[0] you have charged for the entry, which the problem forbids.
• Picking the wrong starting stair: there is no decision to make. The recurrence considers both implicitly because dp[i] for small i already encodes "best of stair 0 and stair 1".

Where this shows up in the enterprise

• Speech recognition (Apple Siri, Google Assistant): the Viterbi algorithm walks a lattice of hidden phoneme states and minimises a cumulative log-loss. Each cell is dp[i] = min over predecessors of dp[prev] + transition_cost. Same shape, much wider lattice.
• Sequence alignment in genomics (Illumina secondary analysis, Oxford Nanopore base-calling, 23andMe ancestry pipelines): Needleman-Wunsch and Smith-Waterman accumulate edit costs across a 2-D lattice, but the row-wise update is the same one-or-two-step minimum.
• NLP tokenisation (HuggingFace BPE, SentencePiece): split a string into the lowest-cost token sequence; dp[i] = best cost to cover the prefix ending at character i.
• PagerDuty oncall rotation pricing: each shift carries a cost, and shift transitions allow one or two-period gaps for legal rest. Minimise total payroll across a quarter.
• Amazon Supply Chain reorder: each replenishment window has a cost; you skip ahead one or two windows depending on demand forecast. The cheapest replenishment cadence is this DP.
• Spell-check suggestions (Google, Microsoft Word): edit-distance minimisation across substitution lattices is structurally the same accumulator.

When a sequence of decisions has bounded look-back and you want the cheapest end-to-end path, this is the template you reach for.

Variants you'll see elsewhere

• climbing-stairs: the counting twin; replace min with +, replace cost addition with 1 to get Fibonacci.
• house-robber: maximise loot with a forbid-adjacency constraint; same skeleton, flipped to max.
• paint-house: 3 colours, no two adjacent the same; the state widens to (i, last_colour) but the recurrence shape is identical.
• decode-ways: count valid 1- and 2-character decodings; once again "look back at most 2".
• triangle and min-falling-path-sum: the 2-D generalisations.

The one-or-two-step look-back is the most common 1-D DP skeleton; once you can write this article's recurrence in your sleep, you have the muscle for the cluster.

How parikshan turns this into a learning loop

min-cost-climbing-stairs is the second rung in the DP ladder. The way to use this article inside the parikshan loop:

1. Read the recurrence above and copy it verbatim into a comment block before you write any code. The discipline of writing the recurrence first is the entire 1-D DP skill.
2. Practice mode with no AI: solve it cold, then ask the practice-mode chat to compare your code against the canonical recurrence. Practice-mode chat is free of integrity penalty and is the right place to ask "is my base case off?".
3. Optimise: if you wrote the O(n) array version, ask the assistant to collapse memory. The assistant should produce the two-variable form; if it cannot, that is a calibration signal about the model on offer that day.
4. Exam mode: redo cold, no AI. Aim for under three minutes from problem read to green submission.
5. Stack the cluster: chain into house-robber immediately, then maximum-subarray. All three share the same one-or-two-look-back skeleton with cosmetic differences.

In the AI-integrated workspace

DP is the domain where AI assistants are simultaneously the most useful and the most likely to ship a subtly broken answer. The classic AI failure mode on this exact problem:

• Wrong base case: a model writes dp[0] = cost[0] because it pattern-matches "you pay something at the start". The code returns answers that are larger than the truth.
• Wrong terminal index: the model returns dp[n-1] instead of dp[n], undercounting by the last stair's potential cost.
• Off-by-one in the cost addition: writes min(dp[i-1] + cost[i], dp[i-2] + cost[i-1]), charging the destination instead of the source.

The 2027 engineer's discipline:

1. State the recurrence aloud before generating code. "dp[i] is what I have paid by the time I arrive at index i. dp[0] = dp[1] = 0. dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])."
2. Tell the agent to implement that exact recurrence. Not "solve min cost climbing stairs"; give it the recurrence.
3. Verify on [10, 15] by hand. dp[2] = min(0 + 15, 0 + 10) = 10. Always do this two-row trace.
4. Ask the agent to roll to O(1) space. This catches whether it actually understood the recurrence: a confused agent cannot do this transformation cleanly.

That discipline turns a probabilistic generator into a deterministic verified result. parikshan's loop is built to train exactly that discipline at scale.