Although this Problem is tagged for DP, But I solved this problem using a simple Combinetorics logic. First I devide the whole thing in two parts viz. even and odd.
For example let n = 10, n/2 = 5 // C(n,k) -> k denotes no. of 2s.
let first way is : 2 + 2 + 2 + 2 + 2 // C(5,5);
second way : (1+1) + 2 + 2 + 2 + 2 // C(6,4);
third way : (1+1) + (1+1) + 2 + 2 + 2 // C(7,3);
...............................................
last way : 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 // C(10,0);
then find the sum of these .
This is my CPP solution.
class Solution {
private:
long long int binomialCoeff(long long int n, long long int k)
{
long long int res = 1;
if ( k > n - k )
k = n - k;
for (long long int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
public:
int climbStairs(int n) {
if(n==0 || n==1){
return 1;
}
if(n%2 == 0){
long long int cnt = 0;
long long int i = n/2,j = n/2;
while(j>=0){
cnt += binomialCoeff(i,j);
i++;
j--;
}
return cnt;
}
long long int cnt = 0;
long long int i = n,j = n;
while(j >= 1){
cnt += binomialCoeff(i,j);
i--;
j-=2;
}
return cnt;
}
};
Time Complexity O(k*n/2);(k for binomialCoeff function) Space Complexity O(1);