大家好，我是年年！今天的內(nèi)容是關(guān)于一道算法題——青蛙跳臺(tái)階。這是一個(gè)面試很喜歡考的題，看到它，大部分人腦海中應(yīng)該立馬出現(xiàn)：斐波那契亞數(shù)列——遞歸——f(n)=f(n-1)+f(n-2)。

但輔導(dǎo)的小伙伴上周在面試中遇到的問(wèn)題是：除了遞歸，能不能寫出別的解法，降低算法的時(shí)間復(fù)雜度。這篇文章給出這道題的更優(yōu)解。

題目

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法？

分析

這是一個(gè)最基礎(chǔ)的動(dòng)態(tài)規(guī)劃類問(wèn)題，首先來(lái)講一下思路：當(dāng)n較小時(shí)，可以直接枚舉得到結(jié)果：

1. n=1時(shí)，青蛙僅有直接跳上一級(jí)臺(tái)階這種跳法，即一種跳法;
2. n=2時(shí)，青蛙可以先跳 上 1 級(jí)，然后再跳 上 1 級(jí)到達(dá)2級(jí)臺(tái)階，；也可以直接跳 2 級(jí)臺(tái)階，即一共有兩種解法;

當(dāng)n較大時(shí)，去枚舉不現(xiàn)實(shí)了。但可以想象一下青蛙“最后一跳”有哪些情況：因?yàn)榍嗤芤淮慰梢蕴?個(gè)或2個(gè)臺(tái)階，所以只可能是兩種情況：從n-1級(jí)跳1級(jí)上去，以及從n-2階的位置跳2級(jí)上去。我們想要知道跳n級(jí)臺(tái)階有多少種解法，只需要知道跳n-1級(jí)臺(tái)階和跳n-2級(jí)臺(tái)階的跳法，把他們加起來(lái)就可以。即得到一個(gè)公式f(n)=f(n-1)+f(n-2)。

常規(guī)解法(遞歸)

看到這個(gè)式子f(n)=f(n-1)+f(n-2)，應(yīng)該很快能反應(yīng)：斐波那契亞數(shù)列，代碼很容易寫出來(lái)。遞歸的關(guān)鍵是確認(rèn)遞歸出口，即：當(dāng)只有1級(jí)臺(tái)階，只有一種跳法；只有2級(jí)臺(tái)階時(shí)，有兩種跳法。

代碼如下：

function frogJump(n) {
  if (n >= 3) {
    let result = frogJump(n - 1) + frogJump(n - 2)
    return result
  } else if (n === 1) {
    return 1
  }else if(n===2) {
    return 2
  }
}
let result = frogJump(6) // 13
console.log(result)

復(fù)雜度分析

上面這張遞歸解法只有60分，因?yàn)闀r(shí)間復(fù)雜度太高。

可以看到，因?yàn)闆](méi)有把結(jié)果保存，出現(xiàn)了很多重復(fù)計(jì)算的步驟：為了得到f(6)的結(jié)果，需要計(jì)算f(5)和f(4),為了得到f(5)的結(jié)果，需要計(jì)算f(4)和f(3)，這里兩次計(jì)算f(4)是獨(dú)立的事件，也就是說(shuō)，我們做了很多重復(fù)工作。

把上面這棵樹(shù)補(bǔ)充成一個(gè)完全樹(shù)，如下：

這種算法復(fù)雜度可以用2^0+2^1+2^2+...+2^4表示，即時(shí)間復(fù)雜度近似為O(2^N)(回憶一下高中數(shù)學(xué)的等比數(shù)列)。

而空間復(fù)雜度是調(diào)用棧的深度，從上面的圖可以看出來(lái)，最大的棧深是n-1，即空間復(fù)雜度是O(n)

進(jìn)階解法（尾遞歸）

上面這種解法時(shí)間復(fù)雜度很高在于做了很多重復(fù)計(jì)算，從遞歸公式能看出來(lái)：f(n)=f(n-1)+f(n-2)=f(n-2)+f(n-3)+f(n-3)+f(n-4)，一生二，二生四，四生八，整個(gè)計(jì)算過(guò)程就像是發(fā)散開(kāi)來(lái)一樣。每一次調(diào)用都沒(méi)有保留下“狀態(tài)”，造成了大量的計(jì)算浪費(fèi)。

只要我們保留下計(jì)算的結(jié)果，就可以把時(shí)間復(fù)雜度控制在O(n)，也就是下面“尾遞歸”。

代碼如下：

function frogJump(first, second, n) {
  let a = first,
  b = second
  let c = first + second
  if (n > 3) {
    a = second
    b = first + second
    return frogJump(a, b, n - 1)
  } else if (n === 3) {
    return c
  } else if ( n === 2) {
    return 2
  } else if(n===1) {
    return 1
  }
}
let result = frogJump(1, 2, 6)
console.log(result)

我們用abc三個(gè)變量，把計(jì)算的結(jié)果保存下來(lái)，避免重復(fù)的工作。從first=1,second=2開(kāi)始計(jì)算，每次遞歸調(diào)用更新first和second的值，這就是在保存下每次計(jì)算的結(jié)果，供下一次遞歸使用。直到n=3，滿足遞歸終止條件。

復(fù)雜度分析

這種尾遞歸，時(shí)間復(fù)雜度只有O(N)，但他是幾種解法里面最難想到，也最難理解的。空間復(fù)雜度即遞歸的深度，是O(N)。

進(jìn)階解法（循環(huán)）

循環(huán)和遞歸是可以相互轉(zhuǎn)化的，所以一種優(yōu)化思路是用循環(huán)把上面的邏輯實(shí)現(xiàn)。

function frogJump(n) {
  if (n === 1) {
    return 1
  } else if(n===2) {
    return 2
  }else {
    let a = 1,
      b = 2,
      c
    let count = 0
    while (count < n - 2) {
      c = a + b
      a = b
      b = c
      count++
    }
    return c
  }
}
let result = frogJump(6)
console.log(result)

我們首先知道了計(jì)算公式f(n)=f(n-1)+f(n-2);并且知道：當(dāng)只有一級(jí)臺(tái)階時(shí)，只有一種解法，只有兩級(jí)臺(tái)階時(shí)，只有兩種解法。如果有三級(jí)臺(tái)階，計(jì)算一次即可（計(jì)算F(3)）；有四級(jí)臺(tái)階，計(jì)算兩次即可（計(jì)算f(3)、f(4)）所以可推，當(dāng)計(jì)算f（n）時(shí)，需要計(jì)算的次數(shù)是n-2，這就是循環(huán)的次數(shù)。上面的代碼便不難寫出。

復(fù)雜度分析

通過(guò)循環(huán)，我們同樣保留下了計(jì)算的結(jié)果，減少了重復(fù)的工作，時(shí)間復(fù)雜度是O(N)?？臻g復(fù)雜度是O(1)。

結(jié)語(yǔ)

通過(guò)這道算法題，能感受到循環(huán)通常比遞歸在時(shí)間復(fù)雜度上有優(yōu)勢(shì)，但它更難想到，代碼塊也會(huì)更復(fù)雜。通常一個(gè)算法的遞歸和循環(huán)是可以相互轉(zhuǎn)化的，可以試著把之前刷過(guò)的題用不同的思路實(shí)現(xiàn)一下。