LeetCode #70 Climbing Stairs 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

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?

中文翻譯

你在爬樓梯，總共有n階才能到達最高處

每次你只能爬1或2階，試問總共有幾種方法可以爬到最高處?

n為介於1到45之間的數字，故不需要考慮步數不在其中的情況

現在來看看範例

官方的範例共兩個，n分別為 2 跟 3

n為2時，共有兩種走法，分別為

• 1+1

• 2 (一次走兩步，一次走完)

n為3時，共有兩種走法，分別為

• 1+1+1

• 1+2

• 2+1

解題思路

首先假設答題函式為Fn(n)

現在先來統整一下已知的事

• n 為 1 時，答案僅有一種 -> 1

• n 為 2 時，答案有兩種 -> 1+1 、 2

現在我們來假設一下 n 為 3 時的情況

首先我們能選擇的僅有兩種可能，一步或兩步對吧

故出現以下兩種分支

• 先走一步，剩下兩步

• 先走兩步，剩下一步

大家有沒有發現剩下的兩種步數我們都知道總共有幾種方法了

分別為Fn(2)= 2 跟Fn(1) = 1

故上面的兩種分支該改為以下

• 先走一步，剩下兩步 Fn(2)= 2
• 先走兩步，剩下一步 Fn(1) = 1

• 故得到結論 : Fn(3) = Fn(2)+Fn(1) = 2+1 = 3

下一個我們換來假設 n 為 4 時的情況

一樣是只能先選擇走一步或兩步

• 先走一步，剩下三步 Fn(3) = 3 (剛剛得到熱騰騰的結論)
• 先走兩步，剩下兩步 Fn(2) = 2

• 故得到結論 : Fn(4) = Fn(3)+Fn(2) = 3+2 = 5

相信這時候，有聰明的小夥伴就看出來了，好像有個規律對不對!

這時候我們來進行最後一次假設，假設 所需步數為 n 時的情況

• 先走一步，剩下 n-1 步 Fn(n-1)
• 先走兩步，剩下 n-2 步 Fn(n-2)

• 故得到結論 : Fn(n) = Fn(n-1)+Fn(n-2)

費波那契數 Fibonacci

這一題其實就是一個經典的費波那契數

修等幾勒，你說你沒聽過

這張圖應該就見過了吧

大家可以觀察上面這張圖會發現每個數字都是由前面兩個數字相加組成

2 = 1+1

3 = 2+1

5 = 3+2

8 = 5+3

等等，這不就跟我們的題目有點像嗎!

更詳細的資料請參閱維基百科

解題思路(程式)

現在讓我們用程式來實現剛剛的想法 (文章會以C#作為範例說明，其他語言不一定會特別解釋)

C# 解決方案

方案1 – 使用變數來儲存

public class Solution {
    public int ClimbStairs(int n) {

        int first  = 1;     //樓梯為1階，僅有1步這種方法
        int second = 2;     //樓梯為2階，有 1+1 、 一次2步 兩種走法
        int tmp = 0;        
        
        if(n<=2)    //若n小於等於2則直接回傳結果(剛好1階2階直接對應至幾種走法)
        {
            return n;
        }
        else
        {
            for(int i =3; i<=n;i++) //每次進入時，會將前兩次之步數加總存於second
            {
                tmp = second;       
                second+=first;      //設second為目前所需步數
                first = tmp;        //設first為上一次所需步數
            }
        }
        return second;
    }
}

方案2 – 使用陣列來儲存

public class Solution {
    public int ClimbStairs(int n) {

        if(n<2){
            return n;
        }
        
        int[] ans = new int[n];
        ans[0] = 1;
        ans[1] = 2;
        
        for(int i=2;i<n;i++) {
            ans[i]=ans[i-1]+ans[i-2];
        }
        return ans[n-1];
    }
}

跟第一個寫法其實差不多，只是使用陣列取代了變數

Java解決方案

方案1

class Solution {
    public int climbStairs(int n) {
        if(n<2){
            return n;
        }
        
        int first  = 1;  
        int second = 2;   
        int tmp = 0;   
        
        for(int i =3; i<=n;i++) {
            tmp = second;       
            second+=first;    
            first = tmp;       
         }
        return second;

    }
}

方案2

class Solution {
    public int climbStairs(int n) {
        if(n<2){
            return n;
        }
        
        int[] ans = new int[n];
        ans[0] = 1;
        ans[1] = 2;
        
        for(int i=2;i<n;i++) {
            ans[i]=ans[i-1]+ans[i-2];
        }
        return ans[n-1];
    }
}

Python3 解決方案

方案1 – 用list來作儲存

class Solution:
    def climbStairs(self, n: int) -> int:
        
        if(n<2):
            return n;
        
        ans = [1,2];
        
        for i in range(2, n):
            ans.append(ans[i-1]+ans[i-2]);
            
        return ans[n-1];

JavaScript 解決方案

方案1

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let arr = [1,2];
    for (var i = 2; i<n; i++) {
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[n-1];
};

結論

這題題目本身其實並不複雜，難的在於如何得出規律。

筆者當初也是抱著頭思考著，突然靈機一動才想到解答!

題目連結 : Climbing Stairs – LeetCode

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我的FaceBook 粉絲專頁按個讚，我會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

*補充 : 與本題相關，算是變形的另一道題目 LeetCode #118 Pascal’s Triangle 解題思路及翻譯 – zyrastory程式美食研究中心

"眾裡尋他千百度，驀然回首，那人卻在，燈火闌珊處"

最新文章

• LeetCode #205 字串是否同構
• LeetCode #66 Plus One 加上一
• LeetCode #290 Word Pattern 單詞樣板(模式)
• LeetCode #206 Reverse Linked List 反轉鏈結串列
• LeetCode #94 Binary Tree Inorder Traversal 中序遍歷二元樹