The idea is simple. If you can solve the problem for n-1 and n-2, you can solve the problem for n easily. The reason I am using a list to store intermediate result is that the solution for a small n would be used multiple times and you don't want to recompute it.

```
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
list = [None] * (n+1)
return self.recur(n, list)
def recur(self, m, list):
if m == 1:
list[1] = 1
return 1
if m == 2:
list[2] = 2
return 2
if list[m] is None:
list[m] = self.recur(m-1, list) + self.recur(m-2, list)
return list[m]
```