## Problem

You are climbing a stair case. It takes n steps to reach to the top.

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

Note: Given n will be a positive integer.

Example:

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

Example 2:

```
Input: 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
```

Although the above answer is in lexicographical order, your answer could be in any order you want.

## Thought Process

The problem can be solved in a recursive way:

## White Board

Below is the white board:

## Code

```
class Solution:
def climbstairs(self, n):
if n == 1:
return 1
if n == 2:
return 2
return self.climbstairs(n-1) + self.climbstairs(n-2)
def test():
cs = Solution().climbstairs(5)
print(cs)
test()
```

```
8
```

## Complexity

- Time complexity is O(2**n), which will TLE (Time Limit Exceeded)

## Optimization

One way to improve this is via memoization.

```
class Solution2:
def climbstairs_m(self, n):
memo = [-1] * (n+1)
if n == 1:
memo[n] = 1
if n == 2:
memo[n] = 2
if memo[n] == -1:
memo[n] = self.climbstairs_m(n-1) + self.climbstairs_m(n-2)
return memo[n]
def test():
csm = Solution2().climbstairs_m(5)
print(csm)
test()
```

```
8
```

The above two solutions will TLE. Another way to optimize is via dynamic programming. Now think about the base case, if there are 0 stairs, there is 1 way: don’t move; if there are 1 stails there’s 1 way. so memo[0] = memo[1] =1

```
class Solution3:
def climbStairs_dp(self, n):
memo = [-1] * (n+1)
memo[0] = 1
memo[1] = 1
for i in range(2,n+1):
memo[i] = memo[i-2] + memo[i-1]
return memo[n]
def test():
csdp=Solution3().climbStairs_dp(5)
print(csdp)
test()
```

```
8
```

Time and space complexities are both O(n) for dynamic programming version.