題目：
你要上樓梯，你一次可以跨過1階、2階或3階
請問到達N階有幾種走上去的方法

舉例：
第2階你可以跨兩次1階到，或乾脆一次跨過2階，所以有2種走法

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

開始前我們先提一件重要的事情：

來源

※警告

請不要在現實中這樣走樓梯
題目效果僅供參考

好，我們開始吧
我們知道，有三個地方分別只要再走1次就會到第N階：

1. 第N-1階（往上跨1階）
2. 第N-2階（往上跨2階）
3. 第N-3階（往上跨3階）

所以第N階的方法數就是把這三階的方法數加起來，而如果N-1, N-2, N-3小於0，則回傳0，當作我們的中止條件（因為題目不包含地下室）

所以我們可以得到下面的程式碼：

static int walkstairs(int stair) {
    if(stair == 0) return 1;
    if(stair < 0) return 0;
    return walkstairs(stair-1) + walkstairs(stair-2) + walkstairs(stair-3);
}

搞定！………了嗎？？

對，搞定是搞定，但一旦stair高起來，整個程式花費的運算資源就會呈指數成長！因為我們每一次call walkstairs()，都會額外再長出三個walkstairs()，然後他們又各長出三個walkstairs()，數字一高就會很可怕！

所以我們可以考慮邊走邊記的方法來處理，先上程式碼再來和大家解釋

static int walkstairs2(int stair) {
    int current = 2;
    int[] steps = {1, 1, 2};
    int newStep;
    if(stair < 0) return 0;
    if(stair==1 || stair==2) return steps[stair];
    while(current < stair) {
        newStep = steps[0] + steps[1] + steps[2];
        steps[0] = steps[1];
        steps[1] = steps[2];
        steps[2] = newStep;
        current++;
    }
    return steps[2];
}

我們逐一和大家解釋這段程式碼的用途：

int current = 2;
int[] steps = {1, 1, 2};
int newStep;
if(stair < 0) return 0;
if(stair==1 || stair==2) return steps[stair];

我們知道這個題目要的是目標階梯的「前三梯分別的方法數」，而每個階梯的方法數都是該階梯的前三階方法數總和。
（好像有點饒舌?）

所以我們可以開一個專門記錄「前三梯方法數」的陣列，一路往上算出方法數

所以一開始我們先把第0、1、2階的數字填上去，然後分別對第0、1、2做return的處理。

那可能會有人好奇steps內的第0階怎麼會是1，這個1是方便我們做處理用的。大家想像一下，第二階是不是第一階+第零階，但第一階是1，第零階是0，這樣不會等於答案啊诶？！

所以我們要補一個1進去，大家可以想像為最一開始要往上走的那一步，這樣子應該就比較好理解了。

while(current < stair) {
    newStep = steps[0] + steps[1] + steps[2];
    steps[0] = steps[1];
    steps[1] = steps[2];
    steps[2] = newStep;
    current++;
}
return steps[2];

這裡就是一路往上爬，我們把前三個方法數加起來，暫時存著。接下來把方法數都往後搬一個，把新的方法數放到最前面，就可以往上爬一階了！

那可能會有人好奇，這兩種方法數會差多少呢？

我們用個簡單好懂的比喻：

• 第一種方法是每次都從起點走到第N-1、N-2、N-3階後再加起來，而且一路上的每一階都是這種要回到起點重算的方法
• 第二種方法是一路走到第N階，同時把第N-1、N-2、N-3階的方法數記好再加起來

如果理解時間複雜度的話，就是O(3^n)及O(n)的差異