Q10.斐波那契数列
题目描述
写一个函数,输入n,求斐波那契数列的第n项。
解题思路
思路一
递归
递归很简单但是并不能AC
python实现代码
class Solution:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
if n == 1:
return 1
return self.Fibonacci(n-1) + self.Fibonacci(n-2)
思路二
动态规划
python实现代码
class Solution:
def Fibonacci(self, n):
# write code here
res = [0]*(n+1)
if n == 0:
return 0
res[0] = 0
res[1] = 1
if n < 2:
return res[n]
for i in range(2, n+1):
res[i] = res[i-1] + res[i-2]
return res[-1]
思路三
循环
python实现代码
class Solution:
def Fibonacci(self, n):
# write code here
f1 = 0
f2 = 1
if n ==0:
return f1
if n == 1:
return f2
for i in range(2, n+1):
f1, f2 = f2, f1 + f2
return f2
以上
今天开学第一天
.0.25