LeetCode 746 · Easy · 1-D Dynamic Programming

Min Cost Climbing Stairs

Stepping on stair i costs cost[i]; from there you climb 1 or 2 stairs. You may start on stair 0 or stair 1. Return the cheapest total to get past the last stair.

O(n)time
O(1)space, in place
back to frontdp in the input array

comma-separated · 2–20 stairs · each cost 0 to 999

cost the input, before the loop rewrites it

cost after the update cost[j] = cheapest fare from stair j to the top · dashed = not final yet

public int minCostClimbingStairs(int[] cost) { int n = cost.length; for (int i = n - 2; i >= 0; i--) { int next2 = i + 2 < n ? cost[i + 2] : 0; // top costs 0 cost[i] += Math.min(cost[i + 1], next2); } return Math.min(cost[0], cost[1]);}
i
—
cost[i] (input)
—
cost[i+1]
—
cost[i+2]
—
answer
—

Why it works

  1. Brute force tries every route: from each stair, recurse on +1 and +2. Routes branch like Fibonacci, so about 1.6ⁿ of them: exponential.
  2. Think from the top down: the cheapest fare from stair i is cost[i] plus the cheaper of the fares from i+1 and i+2. The top is free, and the last stair costs just itself. Fill the table right to left and every value you read is already final.
  3. One pass, no extra table: each stair is updated once from two cells to its right, so O(n) time. The update writes over cost[i], which nobody reads again, so the input array is the table: O(1) extra space.
  4. Pitfall: the answer is Math.min(cost[0], cost[1]), not cost[0]. You may start on either of the first two stairs, and the top is one past the last stair, not the last stair itself.
  5. Related: this is Climbing Stairs with min instead of +. Going front to back works too, with dp[i] = Math.min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2]).