序言

演算法

演算法是一個好的解決問題流程，程式從接收到輸入值在經過處理得到明確的輸出，在電腦科學領域追求著將程序邏輯以更高效的方式處理事情，雖然單個程序的執行消耗可能非常小，但在網站後端或處理大量內容時，演算法的效率會明顯影響系統的延遲和響應速度。對於硬體性能和記憶體有限的嵌入式設備，需要盡可能好的做法來處理內容。

常見的演算法

演算法在這個領域以學習的角度來看實際上就是解題和寫程式，從怎麼用代碼寫出需要的內容，到怎麼用更好的方式來運作，下面將展示一個不同做法的差異。

爬樓梯問題

有一個樓梯有 n 階，每次可以走1或2步，有多少種走法

解法一

說明

• 從第0階開始，每次嘗試走1步或2步
• 對每個可能的選擇再重複同樣的操作，直到到達第n階

C++

class Solution {
public:
    int climbStairs(int n) {
        return climb(0, n);  // 從第0階開始
    }

    int climb(int current, int n) {
        if (current == n) return 1;    // 到達頂層
        if (current > n) return 0;     // 超過頂層
        // 從current爬1步或2步
        return climb(current + 1, n) + climb(current + 2, n);
    }
}

此代碼為LeetCode 70. Climbing Stairs解題範例，輸出在climbStairs函數的return
時間複雜度：O(2ⁿ)，在LeetCode提交可以發現超時了

解法二

說明

• 站在第1階以下的方式只有一種
• 我們保存站在每一階能有多少種方法上來，climb[0] = 1, climb[1] = 1
• 抵達第2階可以是從第1階爬上來的，或是從第0階一次爬2階上來
• 抵達第n階可以是從第n-1階爬上來的，或是從第n-2階爬上來
• 只能從n-1或n-2階上來，互斥事件的方法總和用加法，所以 climb[n] = climb[n-1] + climb[n-2]

C++

#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp = {1, 1};
        for(int i = 2; i <= n ; i++){
            dp.push_back(dp[i-1] + dp[i-2]);
        }
        return dp[n];
    }
};

此代碼為LeetCode 70. Climbing Stairs解題範例，輸出在climbStairs函數的return
時間複雜度：O(n)，在LeetCode提交可以通過

解法三

說明

從輸出結果可以發現這就是一個費波那契數列，我們應該直接貼一個Fibonacci陣列，依據題目的n上限45，所以查找fib[45]的話全部需要46個內容

C++

class Solution {
public:
    int climbStairs(int n) {
        int fib[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};
        return fib[n];
    }
};

此代碼為LeetCode 70. Climbing Stairs解題範例，輸出在climbStairs函數的return
時間複雜度：O(1)，在LeetCode提交可以通過，是最佳解

結論

提升解題能力培養演算法程度，是學習寫程式的良好過程，學會演算法的同時，也能輕鬆的編寫複雜的程式邏輯。