# LeetCode 70: Climbing Stairs

## Problem Restatement

We are given an integer `n`.

There is a staircase with `n` steps. Each time, we may climb either:

1. `1` step
2. `2` steps

We need to return how many distinct ways there are to reach the top.

The official constraint is `1 <= n <= 45`. ([leetcode.com](https://leetcode.com/problems/climbing-stairs/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | Number of distinct ways to reach step `n` |
| Allowed moves | Climb `1` or `2` steps |
| Order matters | `1 + 2` and `2 + 1` are different ways |

Function shape:

```python
def climbStairs(n: int) -> int:
    ...
```

## Examples

For:

```python
n = 2
```

There are two ways:

```text
1 + 1
2
```

So the answer is:

```python
2
```

For:

```python
n = 3
```

There are three ways:

```text
1 + 1 + 1
1 + 2
2 + 1
```

So the answer is:

```python
3
```

For:

```python
n = 4
```

There are five ways:

```text
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
```

So the answer is:

```python
5
```

## First Thought: Recursive Search

A direct way is to think from the current step.

From any position, we can climb either `1` step or `2` steps.

So to count ways to reach step `n`, we can say:

```python
ways(n) = ways(n - 1) + ways(n - 2)
```

because the last move must have come from either step `n - 1` or step `n - 2`.

A direct recursive version looks like this:

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
```

This is logically correct, but it recomputes the same values many times.

For example, `climbStairs(5)` calls `climbStairs(4)` and `climbStairs(3)`. Then `climbStairs(4)` also calls `climbStairs(3)`. The same subproblem appears repeatedly.

## Key Insight

The number of ways to reach step `i` depends only on the previous two steps.

To reach step `i`, the final move must be:

1. From step `i - 1`, by taking `1` step
2. From step `i - 2`, by taking `2` steps

So:

```python
dp[i] = dp[i - 1] + dp[i - 2]
```

This is the Fibonacci pattern.

The base cases are:

```python
dp[1] = 1
dp[2] = 2
```

## Algorithm

If `n <= 2`, return `n`.

Otherwise:

1. Let `prev2 = 1`, the ways to reach step `1`.
2. Let `prev1 = 2`, the ways to reach step `2`.
3. For each step from `3` to `n`, compute:

```python
current = prev1 + prev2
```

4. Move the two previous values forward.
5. Return `prev1`.

## Correctness

For step `i`, every valid path must end with either a `1`-step move from step `i - 1` or a `2`-step move from step `i - 2`.

These two groups do not overlap because their last moves are different. Therefore the total number of ways to reach step `i` is the sum of the ways to reach step `i - 1` and step `i - 2`.

The algorithm starts with the correct values for steps `1` and `2`. Then it computes each later step from the previous two correct values. By induction, every computed value is correct. Therefore the returned value is the number of distinct ways to climb `n` steps.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We compute each step once |
| Space | `O(1)` | We keep only two previous values |

## Implementation

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev2 = 1
        prev1 = 2

        for _ in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1
```

## Code Explanation

Handle the smallest cases first:

```python
if n <= 2:
    return n
```

There is one way to climb one step, and two ways to climb two steps.

Then initialize:

```python
prev2 = 1
prev1 = 2
```

Here:

| Variable | Meaning |
|---|---|
| `prev2` | Ways to reach step `i - 2` |
| `prev1` | Ways to reach step `i - 1` |

For each next step:

```python
current = prev1 + prev2
```

Then slide the window forward:

```python
prev2 = prev1
prev1 = current
```

Finally:

```python
return prev1
```

## DP Array Version

The same idea can be written with a table.

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for step in range(3, n + 1):
            dp[step] = dp[step - 1] + dp[step - 2]

        return dp[n]
```

This version is easier to visualize, but it uses `O(n)` space.

## Testing

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

    assert s.climbStairs(1) == 1
    assert s.climbStairs(2) == 2
    assert s.climbStairs(3) == 3
    assert s.climbStairs(4) == 5
    assert s.climbStairs(5) == 8
    assert s.climbStairs(10) == 89
    assert s.climbStairs(45) == 1836311903

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `n = 1` | Smallest input |
| `n = 2` | Base case |
| `n = 3` | First recurrence case |
| `n = 4` | Small manual example |
| `n = 5` | Confirms recurrence continues |
| `n = 10` | Medium case |
| `n = 45` | Maximum official input |