[70] 爬樓梯

語言: CN / TW / HK

原題地址:https://leetcode-cn.com/problems/climbing-stairs/

70. 爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢?

注意:給定 n 是一個正整數。

示例 1:

輸入: 2
輸出: 2
解釋: 有兩種方法可以爬到樓頂。
1.  1 階 + 1 階
2.  2 階

示例 2:

輸入: 3
輸出: 3
解釋: 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階

 

2 分析

這種場景如果從起步開始分析,將陷入無窮的分支中,從後往前倒推,才是正解。

假設到第n階的次數為F(n),那麼倒推一下,要到第n階,只有兩種方法:從第n-1階再上1階,或者 從第n-2階再上2階(從第n-2階上1階再上1階,這種情況屬於前面那種方法)。那麼我們就有了 F(n) = F(n-1) + F(n-2)。這不就是我們熟悉的 斐波那契數列 的特徵嗎?

那答案就很容易了:

/**
 * 獲取斐波那契數列第n位數大小
 * 
 * @param int $n
 * @return int
 */
function getFibonacciNum(int $n) : int 
{
    // 1,2直接返回
    if ($n < 3)
    {
        return $n;
    }

    $result = 0;
    $x = 1;
    $y = 2;
    $n -= 2; // n如果是3,只運算一次,為了讓$n>0只運算一次就不成立,先減去2
    while ($n > 0)
    {
        $result = $x + $y;
        $x = $y;
        $y = $result;
        $n--;
    }

    return $result;
}

echo getFibonacciNum(4); //輸出5

 

3 後記

這種題目有很多種變形:比如用邊長為1*2的矩形,去填充一個長為n,寬為2的矩形,有多少種方法?這時也是倒推:最後一塊,如果是豎著放的,那剩下的矩形就有F(n-1)種方法;如果最後一塊是橫著放的,那倒數第二塊也必然是橫著放的,那剩下的矩形就有F(n-2)種方法,所以總數也是F(n) = F(n-1) + F(n-2),也是斐波那契數列,原理是一樣的。

分享到: