題目:一段有 100 階的階梯,每次可以跨 1 階或 2 階,請問共有多少種走法?
電話面試遇到這題時,我先是愣了一下,接著自作聰明地想:如果每次都走 1 階,最多 100 步;每次都走 2 階,最少 50 步——明顯跑題了。還好面試官及時打斷,不然我大概會沿著這條死路一路走到黑。
冷靜下來從小數字開始列舉,規律其實很單純:
1 階:只能 1 → 1 種
2 階:1+1 或 2 → 2 種
3 階:1+1+1、2+1、1+2 → 3 種
4 階:1+1+1+1、2+2、2+1+1、1+1+2、1+2+1 → 5 種
也就是 s(n) = s(n-1) + s(n-2)——標準的費氏數列。
為什麼會是費氏?因為最後一步只有兩種可能:跨 1 階(前一狀態是 n-1)或跨 2 階(前一狀態是 n-2),兩者互不重疊且窮盡所有情況,直接相加即可。
var Stairs = new step(); function step(){ this.n1 = 1; this.n2 = 2; this.total = 100; this.getFunction = getFunction; } function getFunction(){ var res = 0; for (var i = 2; i < this.total; i++) { res = this.n1 + this.n2; this.n1 = this.n2; this.n2 = res; } return res; } var totalStairs = Stairs.getFunction(); alert(totalStairs);
這裡刻意避開遞迴,改用迭代滾動兩個變數,時間複雜度 O(n)、空間 O(1)。若寫成 naive 遞迴,100 階會慢到跑不完,因為每層都在重複計算同一批子問題。
function countWays(n) { if (n <= 2) return n; let a = 1, b = 2; for (let i = 3; i <= n; i++) { [a, b] = [b, a + b]; } return b; } console.log(countWays(100)); // 573147844013817000000
順帶一提,這題有個常見變形:如果每次可以跨 1、2 或 3 階,遞推式就變成 s(n) = s(n-1) + s(n-2) + s(n-3),稱為 Tribonacci。掌握「看最後一步有哪些可能」這個思路,這類型的題目都能自己推出來。
我對演算法算不上精通,若有更好的解法也歡迎指正。