[python] O(1) time with general formular


  • 0
    J
    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            import math
            a1 = (1 + math.sqrt(5)) / 2
            a2 = (1 - math.sqrt(5)) / 2
            return int(1/(math.sqrt(5))*(pow(a1, n + 1) - pow(a2, n + 1)))
    

    Actually not very fast in the judgment.
    There are some interesting mathematical proofs about Fibonacci sequence in TAOCP :)


Log in to reply
 

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