Python Sol, although more math than programming.


  • 0
    L

    It's equivalent to find all integer solutions to the equation a + 2b = n and then for each solution count all the permutations of 1's and 2's.
    '''

    class Solution(object):

    def climbStairs(self, n):
        if n == 1:
            return 1
        ones = 0
        twos = int(n / 2)
        if (n % 2 == 1):
            ones = 1
        result = 1
        while twos > 0:
            result += self.nChooseK(ones + twos, twos)
            twos -= 1
            ones += 2
        return result
    
    def nChooseK(self, n, k):
        top = 1
        bot = 1
        for i in range(k):
            top *= n - i
            bot *= i + 1
        return top / bot
    

    ''''


Log in to reply
 

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