# LeetCode 70. Climbing Stairs

## Description

https://leetcode.com/problems/climbing-stairs/

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

The total distinct ways to climb to i th stair is actually the sum of the distinct ways of i – 2 and i – 1 stairs.

## Java Solution

``````class Solution {
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}

int[] ways = new int[n + 1];
ways = 1;
ways = 1;

for (int i = 2; i <= n; i++) {
ways[i] = ways[i - 2] + ways[i - 1];
}

return ways[n];
}
}``````

## Python Solution

``````class Solution:
def climbStairs(self, n: int) -> int:

f = []

f.append(1)
f.append(2)

for i in range(2, n):
f.append(f[i - 1] + f[i - 2])

return f[n - 1]``````
• Time complexity: O(n). Single loop up to n.
• Space complexity: O(n). dp array of size n is used.