上海软件外包公司排名_诸天连锁商城系统_泉州关键词优化排名_深圳疫情最新情况

题目链接

方法一： 递归
方法二： 有记忆的递归：使用memo数组记录之前计算过的值
方法三： 动态规划：for循环 + 使用一个数组记录对应的值
方法四： 动态规划：改进方法三，由于每个值都只需要知道前两个状态值，因此使用两个整数记录对应的值即可，可降低空间复杂度

# 方法一：递归
def Fibonacci(n: int) -> int:if n == 2 or n == 1:return 1result = Fibonacci(n-1) + Fibonacci(n-2)return result

# 方法二：有记忆的递归
def dfs(n,memo):if memo[n] != -1:return memo[n]result = -1if n>2:result = dfs(n-1,memo) + dfs(n-2,memo)memo[n] = resultreturn resultclass Solution:def Fibonacci(self , n: int) -> int:memo = [-1 for _ in range(n+1)]if n>=1:memo[1] = 1 if n >= 2:memo[2] = 1return dfs(n, memo)

# 方法三：动态规划数组
class Solution:def Fibonacci(self , n: int) -> int:if n <= 2:return 1dp = [-1 for _ in range(n+1)]dp[1] = 1dp[2] = 1for i in range(3,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

# 方法四：动态规划+两个整数
class Solution:def Fibonacci(self , n: int) -> int:if n < 2:return 1a,b = 0,1for i in range(2,n+1):a,b = b,a+breturn b