Min Cost Climbing Stairs

House Robber II

Rotate String

Find the cheapest way to reach the top when each stair charges a toll and you may climb one or two stairs.

Given an integer array `cost` where `cost[i]` is the toll charged when you step off stair `i`, return the minimum total toll to reach the top of the floor.

You can start from stair `0` or stair `1`, and from any stair you may climb either one or two stairs. Reaching "the top" means stepping beyond the last stair.

**Input / output**
- Input: `cost: int[]`
- Output: `int` (minimum total toll)

**Examples**
1. `cost = [10,15,20]` returns `15` because starting at stair `1` and paying `15` climbs straight to the top.
2. `cost = [1,100,1,1,1,100,1,1,100,1]` returns `6` by hopping over every stair that charges `100`.
3. `cost = [5,10]` returns `5` because you start on stair `0`, pay `5`, and climb two stairs to the top.

**Constraints**
- `2 <= cost.length <= 1000`
- `0 <= cost[i] <= 999`

**Follow-up**
Can you solve it with `O(1)` extra space by keeping only the two most recent subresults instead of a full DP array?

- 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.

Frame the recurrence

- `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]`.

Tabulate over a DP array

- 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.

Collapse to two rolling variables

- 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.

Optimal O(1)-space scan

Trace `cost = [10,15,20]`.

| i | downTwo | downOne | new step |
|---|---:|---:|---:|
| 2 | 0 | 0 | min(0+15, 0+10) = 10 |
| 3 | 0 | 10 | min(10+20, 0+15) = 15 |

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

Dry run

- 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?

Common mistakes and follow-ups

- 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.

Edge cases to test mentally

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