代码如下:
# 方法一:暴力递归
class Solution:
def fib(self, n: int) -> int:
if n==0:
return 0
if n==1:
return 1
total=self.fib(n-1)+self.fib(n-2)
return total
# 方法二:带备忘录的递归
class Solution:
def fib(self, n: int) -> int:
memo=dict() # 开启备忘录 其实创建了字典用来存会重复计算的结果
def my_fib(x):
if x<2:
if x==1:
return 1
else:
return 0
if x in memo:
return memo[x]
total=my_fib(x-1)+my_fib(x-2)
# 将其结果计入备忘录,下次遇到相同的 直接从字典里进行返回
memo[x]=total
return memo[x]
return my_fib(n)
# 方法三:dp数组迭代求解 (动态规划的原理) 在这道题中 实际上没有涉及到 动态规划的最优化子结构
class Solution:
def fib(self, n: int) -> int:
self.dp=[-1]*(n+1)
if n==0:
return 0
self.dp[0]=0
self.dp[1]=1
for i in range(2,n+1): # 2-1=1 至少能计算1 但n=0 没有包含进去 。不从1开始,是因为1-2 不符合
self.dp[i]=self.dp[i-1]+self.dp[i-2]
return self.dp[n]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)