题目标题
定义Fibonacci数列如下:
0 n=0
f(n)= 1 n=1
f(n-1)+f(n-2) n=2
输入n,用最快的方法求该数列的第n项
Done 动态规划问题 时间复杂度O(n)
参考解析
def fib_re(n):
result = 0
if(n < 1):
print("Wrong input! ")
return -1
else:
if(n == 1 or n == 2):
return 1
else:
return fib_re(n-1) + fib_re(n-2)