剑指offer—面试题10:斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

在没有接触动态规划解法之前，首先想到的就是递归。通过递归 n-1 ,直到 n 为 0、1 的特值。

直接递归

• 原理： 把 f(n)f(n) 问题的计算拆分成 f(n-1)f(n−1) 和 f(n-2)f(n−2) 两个子问题的计算，并递归，以 f(0)f(0) 和 f(1)f(1) 为终止条件。
• 缺点： 大量重复的递归计算，例如 f(n)f(n) 和 f(n - 1)f(n−1) 两者向下递归需要 各自计算 f(n - 2)f(n−2) 的值。

    func fib(_ n: Int) -> Int {
        if (n == 0) {
            return  0
        }
        if (n == 1) {
            return 1
        }
        return fib(n-1) + fib(n-2)
    }

好吧，如果你用这个代码提交到力扣上，直接gg。这种方法太过耗时了。

。

树中存在很多重复的节点，算法中存在很多重复的计算量。优化策略：我们可以将算好的结果缓存起来，如果下次碰到一样的计算项时，我们先可以查找缓存。如果查不到在去计算。会大大的节省计算时间。

记忆化递归

我们可以使用O(n)的空间来存放计算的结果，每次计算可以查找到之前结果，不用重新计算。

  func fib(_ n: Int) -> Int {
        if (n == 0) {
            return  0
        }
        if (n == 1) {
            return 1
        }
        
        var cache = [Int](repeating: 0, count: n+1)
        cache[1] = 1
        
        for i in 2...n {
            cache[i] = cache[i-1] + cache[i-2]
        }
        return cache[n]
    }

动态规划

我们也可以通过动态规划来解决这道问题。目前留个坑，学完动态规划在回来解决。