easy to understand python solution using permutations


  • 0
    J

    Given n, calculate the number of permutations for a pair (x,y), where x is the number of '1' steps and y is the number of '2' steps. Add number of permutations to result. Then, subtract x by 2 and add y by 1, repeat permutation calculation. Keep at it until we've covered all possible pairs of (x,y)

    The key formula here is calculating how many permutations exist for x and y. I found the formula from this stack exchange article to be extremely helpful for these sorts of problems: http://codereview.stackexchange.com/questions/132704/counting-permutations-without-repetitions-for-a-number-or-a-string

    from math import factorial
    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n==0: return 1
            res=0
            two = 0
            while(n>=0):
                res+=self.permutations(n,two)
                n-=2
                two+=1
            return res    
                
            
        def permutations(self,one,two):
            if one==0 or two==0:
                return 1
            k = math.factorial(one+two)
            f = math.factorial(one)*math.factorial(two)
            return k/f
    

Log in to reply
 

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