面試經典問題——每次可以走 1 級或 2 級，上 100 級台階有多少走法

這個問題經常出現在面試中，無論是作為面試官，還是圍觀他人面試，甚至被面試的時候都遇到過這個問題，或者說這種問題的變種。

這個問題標準的描述是。

給定一個有 N 級台階的樓梯，一個人從下到上開始上台階，這個人有兩種上台階的方式：一次上一個台階，一次上兩個台階；

問：從台階底端走到到台階頂端，有多少種上台階的方式？

舉個例子是就是， 3 級台階。一共有 3 種走法。每次上 1 個台階連上三次 / 先上 1 個台階再上 2 個台階 / 先上 2 個台階再上 1 個台階。

遇到這個問題，可以不知道最優解法，但是作為計算機專業方向從業人員。有一個方法是一定要知道的。

窮舉

寫出一個正確的窮舉，有個基本的要求——正確的刻畫狀態轉移。有些面試者，可能是緊張，可能確實基礎不行，描述一個窮舉過程都是錯的，不知道當前計算到哪裡了，接下來應該計算哪個狀態，什麼時候結束。

public static int sum(int step) { //計算 step 台階有幾種走法 if (step < 0) { //step < 0，非法走法，返回 0 return 0; } else if (step == 0) { //最後一步到達起點，返回 1 return 1; } else { //接下來如果先走 1 級的走法 + 先走 2 級的走法 return sum(step - 1) + sum(step - 2); }}

這是一個簡陋的窮舉實現，還有很多其他的實現（優化）方式。但是在這個過程中，如果最後沒有寫出能給出正確結果的邏輯，那麼最希望看到的是一個正確描述窮舉的過程。比如，使用一個多叉樹刻畫窮舉過程，如下圖。

這裡一顆二叉樹，因為每次的選擇都只有兩種可能。事實上，絕大多數窮舉都可以很容易的用多叉樹的形式表述出來，特別是面試的場合，讓人一聽就知道你怎麼想的。那麼可以讓人知道至少有正確的思維。

動態規劃

接下來如果學過動態規劃，那麼很容易的可以發現這個問題可以歸結到子問題的求解上。在遞歸的思想上，動態規劃同樣需求對子問題進行正確的劃分。但相比樸素遞歸演算法的效率低下，動態規劃通過仔細的安排求解順序，對每個子問題只求解一次，並將結果保存下來。那麼隨後再次需要此子問題的解的時候，只需要查找保存的結果，而不必重新計算一次。這是一個典型的時空權衡的例子，它在時間上的節省可能非常巨大——可能將一個指數時間的解轉化為一個多項式時間的解。

同樣的代碼

public static int sum(int step) { if (step < 0) { return 0; } else if (step == 0) { return 1; } else { return sum(step - 1) + sum(step - 2); }}

對於 sum(5)，它的窮舉描述圖為

可以發現，對於剩餘 3 的情況，第三層最左和第二層最右都出現了，在上述的代碼里，每次都要重新計算 sum(3)。如果可以在第一次計算 sum(3) 的時候把結果儲存下來，那麼後續再次計算到 sum(3) 的時候就可以直接返回結果，從而節省大量不必要的計算時間。

public static int sum(int step, int mem[]) { if (step < 0) { return 0; } else if (step == 0) { return 1; } else if (mem[step] != 0) { return mem[step]; } else { int value = sum(step - 1, mem) + sum(step - 2, mem); mem[step] = value; return value; }}public static int sum2(int step, int mem[]) { int i; mem[0] = 1; mem[1] = 1; //為什麼要提前初始化這一項？ for (i = 2; i <= step; i++) { mem[i] = mem[i-1] + mem[i-2]; } return mem[step];}

這裡給出了自頂而下和自底而上兩種方法，使用了一個 數組 來儲存計算結果（注意 mem 邊界，這裡感謝 @砒霜拌辣椒 提出的建議，他認為數組比 HashMap 表達上會更友好）。這個代碼本身是存在優化空間，比如在遞歸中何時判斷當前 step 是否存在，是否應該提前把 0 加入 mem 等；在迭代中，mem 真的需要 step + 1 那麼大么。

在這個過程中，如果學過動態規劃，那麼使用這種方法（備忘錄）是一件很自然而然的事情，因為子結構實在過於明顯。但是在這個過程中，更希望可以看到個人對動態規劃的理解，比如什麼問題適用於動態規劃，什麼是最優子結構，什麼是自頂而下，什麼是自底而上。

《演算法導論》 第四部分 高級設計和分析技術，第 15 章 動態規劃

建議有時間可以多看一下。

斐波那契數列

如果知道這個數列，那麼看上面的遞歸實現，很容易可以發現這就是一個斐波那契數列。N 級台階的走法對應著 Fibonacci(N + 1) 的值。

那麼這個問題就轉化為求解斐波那契數列。

實際上斐波那契數列存在通項公式可以直接求解，即使不使用通項公式，也有很多優化演算法。有興趣可以參考這個鏈接，Program for Fibonacci numbers - GeeksforGeeks。

在這個主題里，其實並不是特別關心斐波那契數列求解有哪些實現，如何優化。所以這個問題在這裡就不展開了。但還是建議閱讀下鏈接中的內容。

--------------------- 題外話的分割線 ---------------------

最後，評論中提到了，int 可以表達 100 級的解么。實際上不能，32 位有符號整型最多表示到 N = 45。那麼 long 可以么，或者說當前語言不是 Java，答案又是如何。

另外收到一個私信，有人問

N 級台階，一次可以走 1 級或者 2 級，但是由於體力有限，如果連續走了 5 次 2 級，就要走 1 級以恢復體力，則有多少種方法？

回復

連續走 5 個 2 級接下來就必須走 1 級，等價於不允許連續出現 6 個 2 級。最樸素的方法，在窮舉的遞歸函數中加上一個參數，代表當前已經連續幾次走 2 級了，比如這個參數名為 count。

if (count < 5) { return sum(n - 1, 0) + sum(n - 2, count + 1); }

else { return sum(n - 1, 0); }

這個代碼不完整，但是邏輯是這樣的。但是這個問題其實可以更深一步，就是是否也適用動態規劃，是否同樣有遞推公式，這裡可以肯定說是有的。具體的過程我不寫了，因為我認為這樣不太好，而且避免你受到我的影響。解決問題從最簡單開始考慮，首先是 1 / 2 / 3 / 4 級台階的答案是什麼，可以手算下。然後考慮 n，總結之前的數字。在推 f(n) 的時候，其中遇到什麼問題，為什麼推不下去。前面遞歸實現中加入了一個額外的 count，那是不是可以推 f(n, count)，然後在推的過程中，這個 count 是不是可以消除掉，遞推公式是什麼，條件有哪些，邊界在哪裡。

這篇文章不是希望提供面試背誦材料，而是希望可以在過程中不斷思考，文章中的代碼有很多可以持續優化的地方，斐波那契數列那個鏈接中也提了好幾種。另外，就像私信中提到那樣，問題可以有變種，除了限制連走特定步數，還有把步數從 1 / 2 改為 2 / 3 / 5 或者其他，除了遞推公式變了，還會引入可行性證明問題，所以並不是很希望把這個問題和斐波那契數列綁定起來，當然，很多優化方式是通用的，等等。一般而言，如果不是純粹秀優越的面試，不會找偏題怪題來為難面試者，如果給不了一個準確結果，那麼很希望看到思考的過程 / 解決問題的方式。

-------- 鏈接的分割線 --------

面試經典問題——如何從非負整數 [0, N) 中等概率不重複地選擇 K 個數

面試經典問題——統計 32 位有符號整型二進位表示中 1 的數目