难度：容易
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)
