The idea of my solution is quite simple.

For a given stair number N, I can have at most N/2 chances to climb 2 steps at one time.

If i choose to climb 2 step for M times and leave the rest climb for 1 step , the total choices I have for this scenario is equal to (choose M from N-M).

Add all possible M up and it's the answer.

The problem is , from n=1 to n=43 , my solution gives the perfect answer , but for n>44 , it's wrong . And after trying the test case , I found several negative answers like n=66,87 and so on . I believe that it's because of the signed bit , cause if n=44 , the correct answer is 1134903170 and is already above half of Math.pow(2,31) ,which is max of int

Anybody know how to get rid of this?

Below is my code

```
public int climbStairs(int n) {
int choice = n/2;
int ans = 1;
for(int i=1;i<=choice;i++){
ans +=choose(i,n-i);
}
return ans;
}
public int choose(int m,int n){
int ans = 1;
for(int i=0;i<m;i++){
ans *= (n-i);
ans /= (i+1);
}
return ans;
}
```