70. Climbing Stairs

這是一個動態規劃的經典題目「爬樓梯」，這個題目根據規則利用「遞迴」其實蠻直覺的。只是遞迴在這個題目中會存在一些效能與重複計算的問題，所以我們試圖從這個例子中觀察遞迴的問題，並且引入一種稱為「動態規劃（Dynamic Programming，DP）」的方法。

先看一下題目描述

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

再搭配範例理解題目

• Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

• Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

本題需要求的是當走到 n 階樓梯時有多少種可能，每一次可以移動一步或兩步。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：遞迴法

根據觀察之後，我們可以會發現「爬第 n 階樓梯的方法數」等於「爬上 n−1 階樓梯的方法數量」 + 「爬上 n−2 階樓梯的方法數量」。根據這樣的觀察與規則之後，很容易就會想到使用遞迴的解法，可以寫出以下的寫法：

f(n) = f(n-1) + f(n-2)

用 Python 實作一次

class Solution:
    def climbStairs(self, n: int) -> int:
        W = [0, 1, 2]
        if len(W) < n:
            W[n] = climbStairs(n - 2) + climbStairs(n - 1);

        return W[n];

也可以用 JavaScript 復刻一次

var climbStairs = function(n) {
    let W = [0, 1, 2];
    if (W.length < n){
        W[n] = climbStairs(n - 2) + climbStairs(n - 1);
    }

    return W[n];
};

方法 ②：動態規劃法

方法一採用遞迴的規則如下：

f(n) = f(n-1) + f(n-2)

這個題目使用遞迴會存在一個問題，就是每次計算 f(n) 之後，會去遞迴計算 f(n-1) + f(n-2)。相同的概念在計算 f(n-1) 會去計算 f(n-2) + f(n-3)、f(n-2) 會去計算 f(n-3) + f(n-4)，以這個例子來看，f(n-3) 會同時在 f(n-1) 和 f(n-2) 重複計算。這樣一來，當 n 很大的時候就會有更多的值會再遞迴過程中重複計算。

因此這裡想法是能不能將剛剛的 f(n-3) 給記錄下來，而不用每一個遞迴過程都重複計算。所以我們想到的是將結果存在一個變數當中（而非每次都計算），將遞迴的過程暫存到一個變數中，如下：

dp[i] = dp[i - 1] + dp[i - 2]

用 Python 實作一次

class Solution:
    def climbStairs(self, n: int) -> int:
        W = [0, 1, 2]
        for i in range(3, n):
            W[i] = W[i - 2] + W[i - 1]
        return W[n]

也可以用 JavaScript 復刻一次

var climbStairs = function(n) {
    var W = [0, 1, 2];
    for (var i = 3; i <= n; i++) {
        W[i] = W[i - 2] + W[i - 1];
    }

    return W[n];
};

反思沉澱

本題的規則是「爬第 n 階樓梯的方法數」等於「爬上 n−1 階樓梯的方法數量」 + 「爬上 n−2 階樓梯的方法數量」，你有沒有覺得這個概念很熟悉？這其實一種稱為「費氏數列」或「斐波那契数列」（Fibonacci）的東西，每一個數回等於前兩個數的總和，這是資工系或是演算法中相當經典的問題。本題可以算是從費氏數列延伸出來的應用，因為相當生活化，並且可以同時使用到「遞迴」與「動態規劃」兩種解法。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 746. Min Cost Climbing Stairs
• 509. Fibonacci Number
• 1137. N-th Tribonacci Number

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。