Min Cost Climbing Stairs – Solution & Complexity

• Let best[i] be the cheapest toll paid to arrive at stair i.
• Arriving at the top means arriving at index n, one past the last stair.
• You reach stair i from either stair i-1 or stair i-2, paying that stair's toll when you leave it.

• best[0] = best[1] = 0 because you may start on either stair for free.
• For every later index, take the cheaper of the two incoming moves and add the toll you paid to make that move.
• The answer is best[n].

• The recurrence only ever looks back two positions, so a full array is unnecessary.
• Track downOne (cost to reach the previous stair) and downTwo (the stair before that) and slide them forward.

• Iterate from index 2 through n, computing each new arrival cost from the two rolling variables, then shift them.
• After the loop, downOne holds the cost to reach the top.

Trace cost = [10,15,20].

The loop ends with downOne = 15, matching the expected answer.

• Returning dp[n-1] instead of dp[n], which stops one stair short of the top.
• Adding cost[i] when arriving instead of cost[i-1]/cost[i-2] for the stair you leave.
• Forgetting that both stair 0 and stair 1 are free starting points.
• Follow-up: how would the recurrence change if you could also climb three stairs at a time?

• The minimum length is 2; the answer is then min(cost[0], cost[1]).
• All-zero tolls cost 0.
• Alternating free and expensive stairs should always land on the free ones.

A single left-to-right scan keeps two rolling subresults. Time is O(n) and extra space is O(1).