basic idea is about think reversely. when I need to reach step n,I may come from n-1 or n-2.so we got a formula, f(n) = f(n-1) + f(n-2). which is the Fibonacci Sequence.

```
int climbStairs(int n) {
if(n<=2) return n;
int p1=2;
int p2=1;
int s =3;
while( s<=n ){
int t = p1;
p1 += p2;
p2 = t;
++s;
}
return p1;
}
```

the way of dp is about current result is base on the result of last 2 steps.

but we use recursion to solve Fibonacci Sequence like problems more commonly.

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