tsanmmmm2000's Tech Blog

Question

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.

Thinking

經典的爬樓梯問題，其實就是一組費氏數列(Fibonacci Polynomial)，理論上我們可以用簡單的遞迴來解決這個問題

public class Solution {
    public int ClimbStairs(int n) {
        return (n == 0 || n == 1) 
            ? 1 
            : ClimbStairs(n - 1) + ClimbStairs(n - 2);
    }
}

但是卻出現TLE(Time Limit Exceeded)的Error，原來n如果夠大，程式會做非常多次重複的運算，導致超出系統的時間限制，因此這題其實是要考動態規劃(Dynamic Programming)，即當一個問題可以被分割為多個子問題(Divide and Conquer)，且這些子問題是不斷地被重複運算，我們選擇將子問題的答案儲存於記憶體空間中(Memoization)，待下次碰到同樣的子問題時可以直接索引，達到空間換取時間的技巧，最常見的例子便是前述的費氏數列(Fibonacci Polynomial)，而它通常有Top-down(遞迴)及Bottom-up(迭代)兩種實作，以下我們先試試前者

public class Solution {
    
    private static int[] temp;
    
    public int ClimbStairs(int n) {
        temp = new int[n + 1];
        return DoFibonacci(n);
    }
    
    private int DoFibonacci(int n)
    {
        if (n == 0 || n == 1) return 1;

        if (temp[n] == 0)
        {
            temp[n] = DoFibonacci(n-1) + DoFibonacci(n-2);
        }
        return temp[n];
    }
}

這兩種實作方式其實沒有絕對的好壞，前者是邊運算邊將結果存放到記憶體空間裡，不會有多餘的運算，但是跑遞迴效能會較差一些；後者則是完全相反，會先運算完所有結果，之後有需要再直接索引，好處是寫起來比較簡潔一些，通常一個迴圈就能搞定。最後就來試試Bottom-up

My C# Solution

public class Solution {
    public int ClimbStairs(int n) {
        var temp = new int[n + 1];
        temp[0] = 1;
        temp[1] = 1;
        for (var i = 2; i <= n; i++)
        {
            temp[i] = temp[i-1] + temp[i-2];
        }
        return temp[n];
    }
}

Reference：演算法筆記 - Dynamic Programming、動態規劃 - Wikipedia