Python Solution beats 96% with Factorial


  • 0
    C

    The basic idea is to get all possible permutations of fixed # of 1 and 2

    from math import factorial
    def climbStairs(self, n):
        res= 0
        two = n//2
    
        for i in range(two+1):
            t = i           # number of twos
            o = n-t*2       # number of ones
            res += factorial(t+o)/(factorial(t)*factorial(o))     # (two+one)!/ (two!*one!)
                
        return res
    

    e.g.
    5 stairs in total, so we get:

    1. 0 two, 5 ones -> 1 permutation
    2. 1 two, 3 ones -> (3+1)!/(3!*1!) = 4 permutations
    3. 2 twos, 1 one -> (2+1)!/(2!*1!) = 3 permutations

    1+4+3 = 8 in total

    This is my first time to post...
    Hope you like my solution :)


Log in to reply
 

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