O(n) with Python: the Fibonacci numbers


  • 0
    Z

    If you notice that the corresponding results of each inputs from 0 to n can constitute the Fibonacci numbers
    i.e. 1,1,2,3,5,8,13,21.....
    everything will be very easy

    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 2:
                return 1
            prev1,prev2 = 0,1
            for i in range(n+1):
                now = prev1 + prev2
                prev2 = prev1
                prev1 = now
            return now
    

Log in to reply
 

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