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

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

題目

一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個n級的臺階總共有多少種跳法？

分析

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

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

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

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

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

代碼如下：

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分，因為時間復(fù)雜度太高。

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

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

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

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

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

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

只要我們保留下計算的結(jié)果，就可以把時間復(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三個變量，把計算的結(jié)果保存下來，避免重復(fù)的工作。從first=1,second=2開始計算，每次遞歸調(diào)用更新first和second的值，這就是在保存下每次計算的結(jié)果，供下一次遞歸使用。直到n=3，滿足遞歸終止條件。

復(fù)雜度分析

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

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

循環(huán)和遞歸是可以相互轉(zhuǎn)化的，所以一種優(yōu)化思路是用循環(huán)把上面的邏輯實現(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)

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

復(fù)雜度分析

通過循環(huán)，我們同樣保留下了計算的結(jié)果，減少了重復(fù)的工作，時間復(fù)雜度是O(N)。空間復(fù)雜度是O(1)。

結(jié)語

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