# My solution using combinatorics (java)

• ``````public class Solution {
public int climbStairs(int n) {
int result=0;

for(int i=0;i<=n/2;i++){
result+=select(n-i,i);
}
return result;
}
``````

The select function calculate C(big,small). The tradtional way to calculate C(big,small) is big!/(small!*(big-small)!). At first, I coded as that as well. But I found that even using long, it is still out of the range. So I did some improvement on the calculation to avoid out of the long range:

1. compare small and big-small, use the biger one to calculate
C(big,small)

2. Instead of calculating any factorial in the method, calculate
big*(big-1)(big-2)....*(small+1) which equals big!/(big-small)!.
But it is still out of range.... So more changes are needed.

3. divide the small! when it can be divided without remainder. I use a
int called record to divide the aa, and decrease record when the
previous record has calculated.

``````public int select(int big,int small){
int another=big-small;
if(another>small){
return select(big,another);
}
else{
long aa=1;
int record=another;
for(int i=big;i>small;i--){
aa*=i;
if(aa%record==0 && record>0){
aa=aa/record;
record--;
}
}

if(record>1){
while(record!=0){
aa=aa/record;
record--;
}
}
return (int) aa;
}

}
``````

}

And my runtime is 168 ms. Yeah! I think this is the benefit to be patient with calculations. :)

• Time complexity is O(N^2). Very slow. Try to make it linear or better.

• To simplify the algorithm, I need to think through it again. I found actually the answer=select(n,0)+select(n-1,1)+select(n-2,2).....+ select(n-i,i) until i<=n/2. So I use an array to store each result from select(n-i,i). Array[i]=select(n-i,i).

And I found that there are some relation between select(big,small) and slect(big-1,small+1).
Select(big,small)=(big-small+2)(big-small+1)/small/(big+1) * slect(big-1,small+1).
because array[small]=Select(big,small), so selectvalues[small]=selectvalues[small-1](big-small+2)/(big+1)(big-small+1)/small;

now the updated code has O(n) complixity no matter in time or space.

``````public class Solution {
long[] selectvalues;
public int climbStairs(int n) {
selectvalues=new long[n/2+1];
int result=0;

for(int i=0;i<=n/2;i++){
result+=select(n-i,i);
}
return result;
}

public int select(int big,int small){
if(small==0){
selectvalues[small]=1;
}
else if(small==big){
selectvalues[small]=1;
}
else{
selectvalues[small]=selectvalues[small-1]*(big-small+2)/(big+1)*(big-small+1)/small;
}
return (int)selectvalues[small];
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.