Climbing Stairs


You may also calculate the possible combinations and sum them up...
But Fibonacci is MUCH better (for this particular case)
Here is my code...
public class Solution {
public int ClimbStairs(int n) {
double combinations = 0;int doubles = n / 2; for (int i = 0; i < (doubles + 1); i++) { combinations += Combination((n  i), (n  (i * 2))); } return (int)combinations; } public double Combination(int n, int p) { if (n.Equals(p)) return 1; return PartFactorial(n, (n  p)) / PartFactorial((n  p), 1); } public double PartFactorial(int n, int take = 1) { double result = 1; if (n.Equals(0)) return result; if (take.Equals(1)) { take = n; } for(int i = 0; i < take; i++) { result *= (n  i); } return result; }
}

I don't know why I was wrong.
When I check the number. I just find if n=6,it could write as 4 groups {all 1, one 2 step, two 2 step, three 2 step}.
And the first group just provides 1 way,
The second group provides 51,
The third group provides 43/2
The fourth group provides 1.It seems as C(ni)(i) for each group.
So I use the below code.class Solution {
public:
int climbStairs(int n) {
int kind = n/2;
int result = 1;
for (int i=1;i<=kind;i++)
{
result +=Combination(ni,i);
}
return result;
}
int Combination(int n, int m)
{
int ans = 1;
for(int i=n; i>=(nm+1); i)
ans *= i;
while(m)
ans /= m;
return ans;
}
};

//I don't know why i was wrong eg:n =3 ans=C(3)(0)+C(2)(1)=1+2=3
//eg:n=4 ans=C(4)(0)+C(3)(1)+C(2)(2)=1+3+1=5
class Solution {
public int climbStairs(int n) {
int two =n/2;
int ans =0;
for(int k = 0;k<=two; k++) {
ans +=countC(nk, k);
}
return ans;
}
private int countC(int m,int k) {
int molecule = 1;
int denominator = 1;for(int i = m;i>mk;i) { molecule *= i; } for(int i = k;i>0;i) { denominator *= i; } return molecule/denominator; }
}