Intuitive recursion approach like "return climbStairs(n -1) + climbStairs(n - 2);" would surely cost too much and lead to TLE. Thus more work are needed when dividing the scale of problem. I cut n into half and then add three situations together. Here's AC code.

```
class Solution {
public:
int climbStairs(int n) {
if(n == 0) return 1;
if(n == 1 || n == 2) return n;
int a = climbStairs(n / 2);
int b = climbStairs((n - 1) / 2 - 1);
int c = climbStairs(n / 2 - 1);
int d = climbStairs((n -1) / 2);
return b * a + d * a + d * c;
}
};
```