題目：

來(lái)源： 力扣（LeetCode）鏈接

寫(xiě)一個(gè)函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項(xiàng)（即 F(N)）。斐波那契數(shù)列的定義如下：

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

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

分析

從題目我們就可以得出一個(gè)公式了，第n的等于第（n-1）的結(jié)果 加上 第（n-2）的結(jié)果

const fib = n => {
  const F = n => {
    return F(n-1) + F(n-2)
  }
  return F(n)
}

但是這樣子F函數(shù)會(huì)無(wú)限遞歸下去，所以我們就要有一個(gè)退出條件，題目也說(shuō)了，就是n = 0 n = 1的時(shí)候有確定的結(jié)果，并且答案需要取模 1e9+7（1000000007），所以，改一下

const fib = n => {
  const F = n => {
    if(n === 1 || n === 0) {
      return n
    }
    let res = F(n-1) + F(n-2)
    return res % 1000000007
  }
  return F(n)
}

這樣子，沒(méi)問(wèn)題，符合題意。

但是，提交的時(shí)候會(huì)發(fā)現(xiàn)超出時(shí)間限制
為什么？仔細(xì)看看
假如n = 100，F(xiàn)(100) = F(99) + F(98)

那么我就要算F(99) 和 F(98)的值:

F(99) = F(98) + F(97)
F(98) = F(97) + F(96)
F(97) = F(96) + F(95)
...
F(2) = F(1) + F(0) = 1 + 0 = 2

在這個(gè)過(guò)程中，我們可以發(fā)現(xiàn)是存在大量的重復(fù)計(jì)算的，每一個(gè)數(shù)字都會(huì)重復(fù)上一個(gè)數(shù)字的計(jì)算的過(guò)程，所以這個(gè)時(shí)長(zhǎng)是非常耗時(shí)的，如下圖的f(n-2) f(n-3) 等等：

F(n).png

function memorize (fn) {
  const cache = {}
  return function(){
    const args = [].slice.call(arguments)
    const key = JSON.stringify(args)
    return cache[key] || (cache[key] = fn.apply(fn, args))
  }
}

const fib = n => {
  const F = n => {
    if(n === 1 || n === 0) {
      return n
    }
    let res = F(n-1) + F(n-2)
    return res % 1000000007
  }
  const cacheF = memorize(F)
  return cacheF(n)
}

再次提交運(yùn)行，發(fā)現(xiàn)還是超時(shí)，再看看代碼，其實(shí)

const cacheF = memorize(F)

這句話只是緩存了F這個(gè)函數(shù)，而F內(nèi)部又遞歸調(diào)用了F，內(nèi)部的F并沒(méi)有被緩存到！
現(xiàn)在看這個(gè)memorize函數(shù)對(duì)存在內(nèi)部自調(diào)用的方法無(wú)可奈何了，也算是備忘錄模式的一個(gè)缺陷吧。但是，這個(gè)緩存的思想我們是可以提取出來(lái)的：

const fib = n => {
  const map = {}
  const F = n => {
    if(n === 1 || n === 0) {
      return n
    }
    if (map[n]) return map[n];
    let res = F(n-1) + F(n-2)
    return res % 1000000007
  }
  return F(n)
}

這樣在遞歸調(diào)用自身的之前先判斷有沒(méi)有緩存，有就直接返回結(jié)果，避免再次調(diào)用耗時(shí)。

提交！通過(guò)！

提交通過(guò).png

嗯，不錯(cuò)，當(dāng)我沾沾自喜的時(shí)候，突然感覺(jué)，就這？有沒(méi)有更好的辦法，除了遞歸外還有其他更好的辦法嗎？？？

答案是有的，上面的解法：（遞歸 + 緩存優(yōu)化） 雖然還可以，但也有個(gè)缺點(diǎn)：緩存需要使用 O(N) 的額外空間

我也想不出更好辦法，于是看了題解，還有一種最適合的方法：動(dòng)態(tài)規(guī)劃！

• 動(dòng)態(tài)規(guī)劃的解法
  首先我們先回憶一下（遞歸 + 緩存優(yōu)化）解法，它的缺點(diǎn)就是需要O(N) 的額外空間，那么利用動(dòng)態(tài)規(guī)劃去解決這個(gè)缺點(diǎn)就不能用遞歸了，因?yàn)槟阌眠f歸的話，還是要緩存來(lái)解決時(shí)間復(fù)雜度的問(wèn)題。那么要怎么解決呢？

首先，我們知道F(n) = F(n-1) + F(n-2), 并且只知道初始的F(0) = 0; F(1) = 1; 對(duì)于后面的數(shù)字n,要求其解的話，只能從n-1, n-2 , n-3一個(gè)個(gè)去往回推算來(lái)求，而這個(gè)過(guò)程又會(huì)存在重復(fù)計(jì)算的問(wèn)題！既然這樣子不好，那么可不可以從前面開(kāi)始 ：0，1，2，3，4 ... n 這樣子往后面推算呢？所以思路如下，0，1我們是知道的，那么就從2開(kāi)始算，2，3，4，... n 采用循環(huán)一個(gè)個(gè)去算，并且后面的結(jié)果依賴(lài)前面的計(jì)算結(jié)果，這樣子只要一個(gè)循環(huán)下來(lái)，從2到n就能求解成功了！上代碼：

const fib = n => {
  if (n === 0 || n === 1) return n
  let a = 0; // a相當(dāng)于  F(n-2)的 n - 2
  let b = 1; // b相當(dāng)于  F(n-1)的 n - 1
  let sum = 0;
  for (let i = 2; i <= n; i++) {
    sum = (a + b) % 1000000007;
    a = b; // 為下一數(shù)字準(zhǔn)備
    b = sum; // 為下一個(gè)數(shù)字準(zhǔn)備
  }
  return sum
}

從上面的代碼可以看出，a代表了n-2, b代表了 n-1 , sum代表了n的解，隨著i的前進(jìn)， a, b也在前進(jìn)。如此一來(lái)后面的數(shù)字依賴(lài)前面的解，環(huán)環(huán)相扣，只需要從2循環(huán)到n就能求出n的解。時(shí)間復(fù)雜度O(N) ；而空間復(fù)雜度呢，因?yàn)橹挥昧薬 b sum 3個(gè)變量，可以看作是O(1)； 而這個(gè)過(guò)程就是動(dòng)態(tài)規(guī)劃！

怎么理解動(dòng)態(tài)規(guī)劃

我的理解就是a\b\sum是固定變量，但是隨著循環(huán)遞增會(huì)不斷的基于該空間復(fù)雜度不變而去不斷的變化其值，這就是動(dòng)態(tài)規(guī)劃！

一個(gè)時(shí)間復(fù)雜度O(N) 空間復(fù)雜度O(1)的解法，確實(shí)是最優(yōu)解了，再優(yōu)你也達(dá)不到時(shí)間復(fù)雜度O(1) 空間復(fù)雜度度O(1); 因?yàn)槟菢幼拥脑捑筒挥糜?jì)算了。

擴(kuò)展

與此題相似的題目還有一道青蛙跳臺(tái)階的問(wèn)題，我剛看的時(shí)候也是沒(méi)有想到是斐波那契數(shù)列，得從后往回推才反應(yīng)過(guò)來(lái)，實(shí)在是巧妙。題目如下：來(lái)源

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請(qǐng)返回 1。

我們?nèi)菀讖牡谝粋€(gè)臺(tái)階開(kāi)始算這個(gè)青蛙可能會(huì)有幾種跳法，這樣子很難想象去求解。所以這里應(yīng)該從后面往回推，如下圖所說(shuō)：

青蛙跳臺(tái)階

其實(shí)這題很多人和我一樣沒(méi)有把它轉(zhuǎn)換為斐波那契數(shù)列。所以想通之后，最終還是同樣的解法，只不過(guò)最開(kāi)始f(0)、 f(1)的值稍有變化罷了。