Hi, this question can be treated as a factorial problem. Let's imagine there are `n`

empty spaces. The `n`

here is the input number. We only can fit in the space with `1`

or `2`

basically. So the base case is that every empty space is filled by `1`

. Then, any two neighbour `1`

can be replaced with one `2`

. When there is only one `2`

in all spaces, we can get the number of different cobinations, which is also the temporary solution. If there are two `2`

in all spaces, we can get another combination. Therefore, this question can be treated as how many combinations of different number of `2`

we can get within `n`

spaces. My python code is put below.

```
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
import math
numof2=n//2
num=0
for i in range(numof2+1):
num+=math.factorial(n-i)/(math.factorial(i)*
math.factorial(n-i*2))
return int(num)
```