Given n, calculate the number of permutations for a pair (x,y), where x is the number of '1' steps and y is the number of '2' steps. Add number of permutations to result. Then, subtract x by 2 and add y by 1, repeat permutation calculation. Keep at it until we've covered all possible pairs of (x,y)

The key formula here is calculating how many permutations exist for x and y. I found the formula from this stack exchange article to be extremely helpful for these sorts of problems: http://codereview.stackexchange.com/questions/132704/counting-permutations-without-repetitions-for-a-number-or-a-string

```
from math import factorial
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n==0: return 1
res=0
two = 0
while(n>=0):
res+=self.permutations(n,two)
n-=2
two+=1
return res
def permutations(self,one,two):
if one==0 or two==0:
return 1
k = math.factorial(one+two)
f = math.factorial(one)*math.factorial(two)
return k/f
```