# LeetCode 746: Min Cost Climbing Stairs

## Problem Restatement

We are given an array `cost`.

`cost[i]` is the price of stepping on stair `i`.

After paying the cost for a stair, we may climb either:

```text
1 step
2 steps
```

We can start from stair `0` or stair `1`.

We need to return the minimum cost needed to reach the top of the floor.

The top is one position after the last stair.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of integers `cost` |
| Output | Minimum cost to reach the top |
| Start position | Stair `0` or stair `1` |
| Move length | `1` or `2` steps |
| Top position | Index `len(cost)` |

Example function shape:

```python
def minCostClimbingStairs(cost: list[int]) -> int:
    ...
```

## Examples

### Example 1

```python
cost = [10, 15, 20]
```

Start at stair `1`.

Pay:

```python
15
```

Then climb two steps to the top.

The answer is:

```python
15
```

### Example 2

```python
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
```

One optimal path pays these stairs:

```python
0, 2, 4, 6, 7, 9
```

Total cost:

```python
1 + 1 + 1 + 1 + 1 + 1 = 6
```

The answer is:

```python
6
```

## First Thought: Try Every Path

From each stair, we can move either one step or two steps.

This creates many possible paths.

A recursive brute force solution would try both choices from every position.

That repeats the same subproblems many times.

For example, the minimum cost from stair `5` may be computed from different earlier paths.

We need dynamic programming.

## Key Insight

To reach stair `i`, the previous stair must be either:

```python
i - 1
```

or:

```python
i - 2
```

So the minimum cost to reach stair `i` depends only on the two previous states.

Let:

```python
dp[i]
```

mean the minimum cost needed to reach position `i`.

Position `i` may be a real stair, or the top.

The top is:

```python
len(cost)
```

To reach `i`, we either come from `i - 1` and pay `cost[i - 1]`, or come from `i - 2` and pay `cost[i - 2]`.

So:

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

The start is free from stair `0` or stair `1`, so:

```python
dp[0] = 0
dp[1] = 0
```

## Algorithm

1. Let `n = len(cost)`.
2. Create `dp` with size `n + 1`.
3. Set `dp[0] = 0` and `dp[1] = 0`.
4. For every position `i` from `2` to `n`:
   - compute the cheaper way to reach `i`.
5. Return `dp[n]`.

## Correctness

`dp[i]` stores the minimum cost to reach position `i`.

For the base cases, `dp[0] = 0` and `dp[1] = 0` are correct because the problem allows us to start from stair `0` or stair `1` without paying before standing there.

For any position `i >= 2`, the last move into `i` must come from either `i - 1` or `i - 2`, because each move climbs one or two steps. If we come from `i - 1`, we must pay `cost[i - 1]`. If we come from `i - 2`, we must pay `cost[i - 2]`.

The recurrence takes the minimum of these two valid possibilities, so it gives the minimum cost to reach `i`.

Since the DP computes positions from smaller to larger, both previous states are already correct when computing `dp[i]`.

Therefore `dp[n]` is the minimum cost to reach the top.

## Complexity

Let `n = len(cost)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We compute one state per position |
| Space | `O(n)` | The DP array stores `n + 1` values |

## Implementation

```python
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            dp[i] = min(
                dp[i - 1] + cost[i - 1],
                dp[i - 2] + cost[i - 2],
            )

        return dp[n]
```

## Code Explanation

We create one DP state for every stair position plus the top:

```python
dp = [0] * (n + 1)
```

The top is index `n`.

The loop starts at `2` because `0` and `1` are free starting positions:

```python
for i in range(2, n + 1):
```

For each position, we choose the cheaper previous step:

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

Finally, return the cost to reach the top:

```python
return dp[n]
```

## Space-Optimized Implementation

Only the previous two DP values are needed.

```python
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        prev2 = 0
        prev1 = 0

        for i in range(2, len(cost) + 1):
            current = min(
                prev1 + cost[i - 1],
                prev2 + cost[i - 2],
            )

            prev2 = prev1
            prev1 = current

        return prev1
```

This version uses constant extra space.

| Metric | Value |
|---|---:|
| Time | `O(n)` |
| Space | `O(1)` |

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minCostClimbingStairs([10, 15, 20]) == 15
    assert s.minCostClimbingStairs(
        [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    ) == 6

    assert s.minCostClimbingStairs([0, 0]) == 0
    assert s.minCostClimbingStairs([1, 2]) == 1
    assert s.minCostClimbingStairs([5, 10, 5]) == 10
    assert s.minCostClimbingStairs([10, 1, 10, 1, 10]) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[10, 15, 20]` | Basic example |
| Long mixed array | Standard dynamic programming case |
| `[0, 0]` | Zero cost stairs |
| `[1, 2]` | Can start from either stair |
| `[5, 10, 5]` | Top can be reached from either final stair |
| Alternating cheap stairs | Checks optimal skipping |