lintcode 366.斐波那契数列

难度：容易

1. Description

366.斐波那契数列

2. Solution

• python
  非递归实现，复杂度O(n)：

class Solution:
    """
    @param n: an integer
    @return: an ineger f(n)
    """
    def fibonacci(self, n):
        # write your code here
        if n==1:
            return 0
        elif n==2:
            return 1
        a,b = 0,1
        for i in range(2,n):
            t = a+b
            a = b
            b = t
        return b

递归实现，复杂度，会超时：

class Solution:
    """
    @param n: an integer
    @return: an ineger f(n)
    """
    def fibonacci(self, n):
        # write your code here
        if n==1:
            return 0
        elif n==2:
            return 1
        return self.fibonacci(n-1)+self.fibonacci(n-2)

3. Reference

1. https://www.lintcode.com/problem/fibonacci/description