JS solution using binomial coefficient.


  • 1
    R
    var climbStairs = function(n) {
        maxTwo = Math.floor(n/2);
        res = 0;
        for(var i = 0; i <= maxTwo; i++) {
            binK = Math.min(i, n-i);
            binN = Math.max(i, n-i);
            res += fac(binN) / (fac(binK) * fac(binN-binK)); //binomial coefficient
        }
        return res;
    };
    
    //calculate n!
    function fac(n) {
        ans = 1;
        while(n > 0) 
            ans *= n--;
        return ans;
    }
    

    Iterates through all possible numbers of double and single steps. Using binomial coefficient on each iteration to calculate number of combinations of the given number of single and double steps.


Log in to reply
 

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