題目

https://leetcode.com/problems/climbing-stairs/

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

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

Example 2:

Input: 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

解答

C#

public class Solution {
    public int ClimbStairs(int n)
    {
        double a1 = 1 / Math.Sqrt(5);
        double b2 = Math.Pow((1 + Math.Sqrt(5)) / 2, n + 1);
        double c3 = Math.Pow((1 - Math.Sqrt(5)) / 2, n + 1);
        int fx = (int)(a1 * (b2 - c3));
        return fx;
    }
}

結果

Runtime: 36 ms, faster than 96.60% of C# online submissions.

Memory Usage: 14 MB, less than 5.88% of C# online submissions.

Time Complexity: O(log n)

Space Complextiy: O(1)

為什麼我要這樣做？

我覺得這題有點難，應該超過 easy 的程度吧？至少我在寫 code 之前就花了不少時間找規律。

除了 n = 1 及 n = 2 之外，我將每個 n 用樹狀的方式去找，並計算每個 n 應該會有幾種結果，如下

n = 3

111   // 1個3個的數字組合
21    // 2個2個的數字組合
12

結果： 1+2 = 3

n = 4

1111 // 1個4個的數字組合，C4取0 = 1
211  // 3個3個的數字組合，C3取1 = 3
121
112
22   // C2取2 = 1

結果： 1+3+1 = 5

n = 5

11111 // C5取0 = 1
2111  // C4取1 = 4
1211
1121
1112
221   // C3取2 = 3
212
122

結果： 1+4+3 = 8

n = 6

111111 // C6取0 = 1
21111  // C5取1 = 5
2211   // C4取2 = 6
2121
2112
1221
1212
1122
222    // C3取3 = 1 

結果： 1+5+6+1 = 13

n = 7

1111111 // C7取0 = 1
211111  // C6取1 = 6
22111   // C5取2 = 10
2221    // C4取3 = 4 

結果： 1+6+10+4 = 21

n = 8

11111111 // C8取0 = 1
2111111  // C7取1 = 7
221111   // C6取2 = 15
22211    // C5取3 = 10
2222     // C4取4 = 1

結果： 1+7+15+10+1 = 34

1, 2, 3, 5, 8, 13, 21, 34...
發現算出的結果有規律 ── 每一個結果剛好是等於前一個結果再加前前一個結果。

歸納出的公式為

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

再來就是用 暴力法 (Brute Force) 解決，去驗證我的想法是否正確

public class Solution {
    public int ClimbStairs(int n) {
    {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return ClimbStairs(n - 1) + ClimbStairs(n - 2);
    }
}

以上使用 遞迴(Recursion) 去查找，當使用者輸入 n 時，再去找 n - 1 及 n - 2 的結果，直到 n = 1 或 n = 2。

此時的時間複雜度 (Time Complexity) 是 O(2^n)。

因為 f(8) 時要查找並相加約 2^8 的結果
f(7) 時要查找並相加約 2^7 的結果
f(6) 時要查找並相加約 2^6 的結果
f(5) 時要查找並相加約 2^5 的結果 ... 以此類推。

後來送出 submission 時又被 LeetCode 退回了，效能太差了～～～
就思考有沒有一個 迴圈 就可以算出的解答？

int ClimbStairs(int n) {
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;

    int result = 0;
    int pre = 1;
    int next = 2;

    for (int i = 2; i < n; i++)
    {
        result = pre + next;
        pre = next;
        next = result;
    }
    return result;
}

1. 迴圈跳過 n = 1 及 n = 2 開始算起
2. 迴圈裡 result 等於前前一個 pre 加前一個 next
3. 前前一個 pre 改成原本的前一個 next
4. 前一個 next 改成剛計算好的 result
5. 上述3. 4. 讓下一次的迴圈計算使用，直到算到 n 為止

此時的時間複雜度 (Time Complexity) 為 O(n)。

然後我又思考「應該有公式可以推導吧？」、「這不是很像鼎鼎大名的 費氏數列 (Fibonacci Sequence) 嗎！」

我就上網找了費氏數列的公式，如下

只是費氏數列是1, 1, 2, 3, 5, 8 ... 多一個1，因此我需要將公式的 n 次方 改為 n + 1次方，而且只利用 Math 的 method，答案就這樣算出來了 !

不過蠻多人說 Math.Pow 的時間複雜度 (Time Complexity) 為 O(1)，不過實際上應該趨近於 O(log n)，

可以參考 Write a program to calculate pow(x,n) 的寫法去了解為什麼，我就不多加說明了～

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉