LC 70. Climbing Stairs

Nilanjan Deb · April 1, 2020

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);



Dicussion Forum