509. 斐波那契数

这个题目根据题意，暴力解法就是一个简单的递归，求$fib(n)$的值，我们求$fib(n-1)+fib(n-2)$就可以了。当n是0,1,2的时候就是fib函数的一个基础状态。终止递归的条件。但是这个效率很低，时间复杂度是$O(2^n)$。

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)

但是我们可以发现，效率低的原因是造成了多次的重复计算，例如我们求$fib(5)$,就要求$fib(4)$和$fib(3)$,而$fib(4)$又需要求$fib(3)$和$fib(2)$，这里的$fib(3)$就重复计算了，包括其他的一些中间状态也有可能会被多次计算。那我们就可以做一个备忘录，要计算一个值，先看看之前是不是算过了，算过就不用重复算了，如果没有算过，就算一下，存到备忘录里面，然后再返回这个值。因为没有了重复计算，每个$fib(n)$都只需要计算一次就行了。时间复杂度直接从$O(2^n)$降低到了$O(n)$，提升非常的巨大。

class Solution:
    def fib(self, n: int) -> int:
        memo = [-1 for _ in range(n + 1)]
        return self.func(n, memo)

    def func(self, n, memo):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1
        if memo[n] != -1:
            return memo[n]
        memo[n] = self.func(n - 1, memo) + self.func(n - 2, memo)
        return memo[n]

当然，上面是递归的写法，我们还可以使用一个简单的for循环通过迭代的写法来解决这个问题。

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        fib_n_1 = 1
        fib_n_2 = 0
        fib_n = 0
        for i in range(2, n + 1):
            fib_n = fib_n_1 + fib_n_2
            fib_n_2 = fib_n_1
            fib_n_1 = fib_n
        return fib_n