First I used recursion and found that it cost too much time. The recursive version is like this:

```
public int climbStairs(int n) {
if (n <= 1)
return 1;
return climbStairs(n - 1) + climbStairs(n - 2);
}
```

I found that recursion will count the previous results every time and cost too much time. Therefore, I was wondering if I can save the previous results in an array and then I came out this method:

```
public int climbStairs(int n) {
if (n <= 1)
return 1;
int[] a = new int[n + 1];
a[0] = 1;
a[1] = 1;
for (int i = 2; i <= n; i++) {
a[i] = a[i-1] + a[i-2];
}
return a[n];
}
```

It is quite effective and I compare it with the recursive version. When n=44, the recursive one cost 4653ms to finish while this method cost less than 0ms.