今天解的題目是第七十題 Climbing Stairs。題目要求計算一個人要爬上總共有 n 階的樓梯，每次可以選擇爬一階或兩階，總共有多少種不同的方法能到達頂端。舉例來說，如果樓梯有 3 階，走法有三種：走 1+1+1、先 2 再 1、或是先 1 再 2。你會發現，要走到第 i 階只有兩種可能：一種是從第 i-1 階走一步上來，另一種是從第 i-2 階跨兩步上來，所以「第 i 階的方法數 = 第 i-1 階的方法數 + 第 i-2 階的方法數」。這個規律其實就像斐波那契數列一樣。程式的做法是先處理基礎情況：如果樓梯只有 1 階，那就只有 1 種方法；如果有 2 階，就有 2 種方法。接下來用一個陣列 dp 來記錄每一階的方法數，按照上面的規律一路加上去，最後算到第 n 階就是答案。這題的關鍵在於發現它跟斐波那契的遞推關係相同，用動態規劃就能很快得到結果。
iThome鐵人賽
看影片追技術