```
public class Solution {
public int choose(int n, int k){
if (k <= 0)
return 1;
return (int) (1L * n * choose(n - 1, k - 1) / k);
}
public int climbStairs(int n) {
int t = n + 1 >> 1;
int p = n - t;
int sum = 0;
for (int i = 0; i <= p; i++)
sum += choose(n - i, i);
return sum;
}
}
```