variation of Fibonacci, O(n) time, O(1) space

  • 0

    Basic idea is, f(n) = f(n-1) + f(n-2). f(1)=1, f(2)=2

    class Solution(object):
        def climbStairs(self, n):
            if n==1: return 1
            if n==2: return 2
            a, b = 1, 2
            for i in xrange(2, n):
                a, b = b, a + b
            return b

Log in to reply

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