Basic Problemsminimizationlinear

Weighted Climbing Stairs

Each step of an n-step staircase carries a cost to land on it, and a move advances 1 or 2 steps at a time. Find the cheapest total cost to reach the top, starting from either of the first two steps for free.

Do this lesson first: climbing stairs

Example input

cost = [10, 15, 20, 10, 5, 25, 30, 10, 5, 15], n = 10

Expected output

75

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

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

Ask what the last move into stair i could have been: a step of 1 from stair i - 1, or a step of 2 from stair i - 2. Either way you pay cost[i - 1] the instant you land on stair i, on top of whichever predecessor already cost less, so the recurrence takes a min over the two arrival routes and then adds that one landing cost once.

dp[0] = 0 and dp[1] = cost[0] are given directly, and they pin the cost convention this table uses: cost is charged for LANDING on a stair, never for leaving one. Standing on the ground before any step is free, since nothing has been landed on yet, while dp[1] already carries cost[0], the price of arriving at stair 1. Every other cell depends only on smaller indices, so filling left to right guarantees both predecessors already hold a real value before they are read.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0 and dp[1] = cost[0] are given directly, and they pin the cost convention this table uses: cost is charged for LANDING on a stair, never for leaving one. Standing on the ground before any step is free, since nothing has been landed on yet, while dp[1] already carries cost[0], the price of arriving at stair 1. Every other cell depends only on smaller indices, so filling left to right guarantees both predecessors already hold a real value before they are read.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

0

10

15

30

25

30

50

60

65

75

weighted-climbing-stairs.ts

1function minCostClimbingStairs(cost) {
2 const dp = [0, cost[0]];
3 for (let i = 2; i <= cost.length; i++) {
4 dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i - 1];
5 }
6 return dp[cost.length];
7}

Base caseComputedBeing readAnswer

The code, the trap, the variations

weighted-climbing-stairs.ts

1function minCostClimbingStairs(cost) {
2 const dp = [0, cost[0]];
3 for (let i = 2; i <= cost.length; i++) {
4 dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i - 1];
5 }
6 return dp[cost.length];
7}

Where people go wrong

Assuming cost is paid on leaving a stair instead of on landing on it. Sources disagree here, and the two conventions give different totals from the same cost array: under a leaving-cost reading, the top stair's own cost would never be charged, since there is nothing left to leave from, while under this table's landing-cost reading dp[0] carries no charge even though every stair after it does, because nothing was ever landed on at the ground floor. This table pays on landing: dp[0] = 0, and every dp[i] for i >= 1 includes cost[i - 1]. Compare against a source using the other convention and every value beyond dp[1] will look shifted.

Pay each stair's cost when leaving it, instead of when landing on it.
The recurrence shifts by one index: dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]), since the charge now belongs to the stair departed rather than the one arrived at. Which two cells are read stays the same; only which cost index attaches to which term moves.
Count the number of cheapest-cost routes to the top, instead of just the cheapest cost.
combine would need to carry a companion count alongside the minimum cost, tracking how many routes achieve it, a genuinely different state than a bare number; the same two predecessors still feed it.

Climbing Stairs with 3 Moves Maximum Segments