斐波那契數(shù)列

題目描述

寫一個函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項。斐波那契數(shù)列的定義如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出。

答案需要取模 1e9+7（1000000007），如計算初始結(jié)果為：1000000008，請返回 1。

示例：

輸入：n = 2
輸出：1

輸入：n = 5
輸出：5

提示：
0 <= n <= 100

轉(zhuǎn)載來源：力扣（LeetCode）

題目分析

斐波那契數(shù)列大概是每位計算機人接觸的第一個遞歸思路的題了吧，這里就不展開講怎么推導(dǎo)了，直接給出方程：

• n == 0 -> return 0
• n == 1 -> return 1
• else -> fib(n - 1) + fib(n - 2)

這種做法就是典型的遞歸做法，它很好理解，也很快就能將代碼寫出來，但是有兩個缺點：

1. 重復(fù)計算，如下所示，計算fib(4)，需要fib(3)和fib(2)，而fib(3)又需要fib(2)，重復(fù)計算了fib(2)
   1.1 fib(4) = fib(3) + fib(2)
   1.2 fib(3) = fib(2) + fib(1)
   1.3 fib(2) = fib(1) + fib(0)

2. int 溢出，在Java里，int是32bit的，其中最高位是符號位，所以int范圍是-2147483648~2147483647，在n足夠大的時候，int分分鐘被爆掉

優(yōu)化：

• 犧牲空間來換取時間
  對于重復(fù)計算的問題，我們可以利用內(nèi)存來保留先前已經(jīng)計算的結(jié)果，例如fib(4)里求得了fib(2)，在求fib(3)的時候就不要再算一遍fib(2)，直接從內(nèi)存里獲取就好
• 取余式儲存
  在這里通過舉例子來說明：{
  ?3、4、5 求和，結(jié)果對2取余
  ?3 mod 2、4 mod 2、5 mod 2，結(jié)果求和，再對2取余
  }
  以上結(jié)果是一樣的，數(shù)學(xué)證明也很簡單，（ax + 1）+（bx + 0）+（cx + 1）的結(jié)果就是（a + b + c）x + 1 + 1，其中x就是要取余的數(shù)，取余只是早取晚取的區(qū)別而已

但是，凡事都有但是，越早取余運算量就越大，計算機系統(tǒng)的知識告訴我們，取余和除法其實是一致的，需要的時鐘周期數(shù)遠(yuǎn)遠(yuǎn)大于加減法，所以計算fab(10)就對每一項結(jié)果都進行取余可能會造成過多的性能損耗。

    fun fib(n: Int): Int {
        if (n == 0 || n == 1) return n
        val array = IntArray(n + 1){0}
        array[0] = 0
        array[1] = 1
        for (i in 2 until n) {
            array[i] = (array[i - 1] + array[i - 2]) % 1000000007
        }
        return array[n]
    }