Python with factorial idea


  • 0
    E

    Hi, this question can be treated as a factorial problem. Let's imagine there are n empty spaces. The n here is the input number. We only can fit in the space with 1 or 2 basically. So the base case is that every empty space is filled by 1. Then, any two neighbour 1 can be replaced with one 2. When there is only one 2 in all spaces, we can get the number of different cobinations, which is also the temporary solution. If there are two 2 in all spaces, we can get another combination. Therefore, this question can be treated as how many combinations of different number of 2 we can get within n spaces. My python code is put below.

    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            import math
            numof2=n//2
            num=0
            for i in range(numof2+1):
                num+=math.factorial(n-i)/(math.factorial(i)*
                    math.factorial(n-i*2))
    
            return int(num)
    

Log in to reply
 

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