备忘录解法
class Solution:
def Fibonacci(self, n):
# write code here
mem = [-1 ]*(n+1)
return self.DieDai(n, mem)
def DieDai(self, n, mem):
if n == 1: return 1
if n == 0: return 0
if mem[n] > -1: return mem[n]
mem[n]=self.DieDai(n - 1, mem) + self.DieDai(n - 2, mem) # 卧槽，备忘录忘记记录了，怪不得时间还变慢了
return mem[n]
重复递归解法，但是没想到计时发现备忘录还没有普通的递归快。。。后来发现是备忘录忘记记了，头冷。本质上是自顶向下的动规，但是重复问题多，时间复杂度特别大
class Solution:
def Fibonacci(self, n):
# write code here
if n == 1: return 1
if n == 0: return 0
return self.Fibonacci(n - 1) + self.Fibonacci(n - 2)
循环，本质上是自底向上的动规
class Solution3:
def Fibonacci(self, n):
# write code here
dp=[]
for i in range(n+1):
if(i==0):dp.append(0)
elif(i==1):dp.append(1)
else:dp.append(dp[i-1]+dp[i-2])
return dp[n]
