（补）算法刷题Day25：BM62 斐波那契数列

题目链接

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

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

# 方法二：有记忆的递归
def dfs(n,memo):
    if memo[n] != -1:
        return memo[n]
    result = -1
    if n>2:
        result = dfs(n-1,memo) + dfs(n-2,memo)
    memo[n] = result
    return result

class 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] = 1
        return dfs(n, memo)

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