iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 20
1
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 20

【從面試題學邏輯-20】你玩過小朋友下樓梯,那有玩過小朋友上樓梯嗎?(CTCI 8.1 小朋友上樓梯)

題目:
你要上樓梯,你一次可以跨過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)的差異


上一篇
【從面試題學邏輯-19】幫你自己次方一下(leetcode 50. Pow(x, n))
下一篇
【從面試題學邏輯-21】如何邊吃甜甜圈邊理解河內塔程式的遞迴概念?(CTCI 8.6 河內塔)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言