## Table of contents

## Open Table of contents

## Problem

You are climbing a staircase. It takes `n`

steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**Example 1:**

```
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
```

**Example 2:**

```
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
```

**Constraints:**

`1 <= n <= 45`

## Explanation/Approach

This problem can be approached using Dynamic Programming. The key is to recognize that the number of ways to climb to the top is the sum of the ways to climb to the step before the last and the step before that. This is because at each step, you can either climb 1 or 2 steps.

- If you are one step away from the top, you could have gotten there by taking a single step from the second last step.
- If you are two steps away, you could have reached the top by taking two single steps or one double step.

This forms the basis of the Fibonacci sequence, where `dp[i] = dp[i-1] + dp[i-2]`

.

## Solution: Dynamic Programming

```
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
```

**Time and Memory Complexity**

The time complexity is O(n), as we need to fill the array of size `n`

. The space complexity is also O(n) due to the space used by the `dp`

array.

**Explanation**

The solution initializes a `dp`

array to store the number of ways to climb to each step. It then iteratively fills this array using the relationship `dp[i] = dp[i-1] + dp[i-2]`

. For `n = 3`

, the array `dp`

will be `[0, 1, 2, 3]`

, where `dp[3]`

is the answer, indicating 3 distinct ways to climb to the top.

**Visual Representation**

Consider `n = 3`

:

```
Step 1: Only 1 way (1 step)
Step 2: 2 ways (1 step + 1 step, 2 steps)
Step 3: dp[2] + dp[1] = 2 + 1 = 3 ways
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
```

Certainly! Let’s extend the visual representation and explanation for `n = 5`

steps.

**Extended Explanation**

For `n = 5`

, we need to calculate the number of distinct ways to climb a staircase with 5 steps. To do this, we use the dynamic programming approach, leveraging the Fibonacci-like pattern that emerges in the problem.

- The base cases are:
`dp[1] = 1`

(only one way to climb one step).`dp[2] = 2`

(two ways to climb two steps:`1+1`

or`2`

).

- For every step
`i`

from 3 to`n`

, the number of ways to reach step`i`

is the sum of the ways to reach step`i-1`

and step`i-2`

. This is because you can reach step`i`

either from step`i-1`

by taking one more step, or from step`i-2`

by taking a two-step jump.

**Visual Representation for n = 5**

Let’s break down the steps:

**Step 1**:- Ways to reach: 1 (1 step).

**Step 2**:- Ways to reach: 2 (1+1, 2).

**Step 3**:- Ways to reach:
`dp[2] + dp[1] = 2 + 1 = 3`

(1+1+1, 1+2, 2+1).

- Ways to reach:
**Step 4**:- Ways to reach:
`dp[3] + dp[2] = 3 + 2 = 5`

(1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2).

- Ways to reach:
**Step 5**:- Ways to reach:
`dp[4] + dp[3] = 5 + 3 = 8`

(1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1).

- Ways to reach:

So, for `n = 5`

, there are 8 distinct ways to climb to the top of the staircase.