Dynamic programming

Min cost stairs · source
1function minCost(cost: number[]) {
2 const n = cost.length;
3 const dp = new Array(n).fill(0);
4 dp[0] = cost[0];
5 dp[1] = cost[1];
6 for (let i = 2; i < n; i++) {
7 dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
8 }
9 return Math.min(dp[n - 1], dp[n - 2]);
10}
Min cost stairs · liveEach step's answer is built from two answers you already have.

Base case: standing on step 0 costs its own price, 42.

1 / 23

How min cost stairs works

You climb a staircase paying each step's cost, moving 1 or 2 steps at a time, starting from step 0 or 1, and you may finish off the end from either of the last two steps. The question “what is the cheapest way to stand on step i?” has a tiny answer: you arrived from i−1 or i−2, so it is cost[i] plus the cheaper of those two already-solved answers. That equation — the recurrence — is the entire algorithm.

This is dynamic programming with all the mystery removed: an overlapping-subproblem structure (naive recursion would recompute the same steps exponentially often) collapsed into one left-to-right pass, because by the time you reach step i, both answers it depends on are sitting in the table. Watch the dp labels fill under the bars — each one computed once, from two neighbours, never revised.

Two habits to build here that carry to every DP: read the recurrence out loud before coding (if you cannot state it, the code will not save you), and notice the space optimization — dp[i] only looks back two slots, so two variables replace the whole array, O(n) → O(1). Interviewers ask for that follow-up almost every time.

space play / pause · ←→ step

Complexity

timeO(n)
spaceO(n) → O(1)
recurrencedp[i] = cost[i] + min(dp[i−1], dp[i−2])
pattern1-D bottom-up