It's equivalent to find all integer solutions to the equation a + 2b = n and then for each solution count all the permutations of 1's and 2's.

'''

class Solution(object):

```
def climbStairs(self, n):
if n == 1:
return 1
ones = 0
twos = int(n / 2)
if (n % 2 == 1):
ones = 1
result = 1
while twos > 0:
result += self.nChooseK(ones + twos, twos)
twos -= 1
ones += 2
return result
def nChooseK(self, n, k):
top = 1
bot = 1
for i in range(k):
top *= n - i
bot *= i + 1
return top / bot
```

''''