My first approach is DP because this is an optimization problem. So if we have the maximum way at "n-1" steps then the optimal steps at "n" is:

We step like the n times different before then with another step -> optimal way with n-1 steps

We step (n-1) times different before then the last 2 steps by once -> optimal way with n-2 steps

Then we have: max[n] = max[n-1] + max[n-2] -> turn out it is a Fibonacci! XD

```
int climbStairs(int n) {
if (n==0) return 0;
if (n==1) return 1;
if (n==2) return 2;
int oldWay1 = 1;
int oldWay2 = 2;
int way;
for (int i=3; i <=n; i++) {
//DP[i] = DP[i-1] + DP[i-2];
way = oldWay1 + oldWay2;
oldWay1 = oldWay2;
oldWay2 = way;
}
return way;
}
```