演算法系列：斐波那契數列問題

2022 年 11 月 15 日
筆記
演算法

問題描述：

　　假設有個樓梯，每次只能走3步或者5步，問到達第N節會有幾種組合？

思路分析：

　　這個問題需要反過來思考才能比較容易的找到規律。總共有N級台階，因為每次要麼上3階要麼上5階，因此對於第N級台階來說，它的前一步要麼是在N-3階處要麼是在N-5階處。在N-3階處時上3階到N級台階，在N-5階處時上5級到N級台階。因此，可以用公式表示為f(n)=f(n-3)+f(n-5)，這就變成了一個典型的遞歸了。像這種公式，在數列中有一個比較著名的數列叫做「斐波那契數列」，當然這裡是3和5可以看做是一種變形的「斐波那契數列」；如果把3和5變成1/2就是完美的斐波那契數列了；

補充：斐波那契數列是滿足F(n)=F(n-1)+F(n-2) 的數列

好了既然分析出規律了，那麼我們用程式碼實現以下

方法一：遞歸實現

時間複雜度：O(!n)　

    public static int countStep(int n) {
        if (n < 3) {   //當n小於最小階數時，沒有可能的方案
            return 0;
        } else if (n == 3) {   //當前值等於3時.只有一種可能
            return 1;
        } else if (n > 3 && n < 5) {//當前值大於3並且者小於5時.沒有可能的方案
            return 0;
        } else if (n == 5) {  //當n==5時只有一種可能
            return 1;
        } else {  //n>5時，採用遞歸的方式進行計算
            return countStep(n - 3) + countStep(n - 5);
        }
    }

方法二：動態規劃

　　方法一種的單純遞歸的時間複雜度過高，我們可以將之前計算過的結果存放到map中，如果之後map中存在則直接獲取；

    public static int climbStairs(int n, Map<Integer, Integer> map) {
        if (n < 3) {   //當n小於最小階數時，沒有可能的方案
            return 0;
        } else if (n == 3) {   //當前值等於3時.只有一種可能
            return 1;
        } else if (n > 3 && n < 5) {//當前值大於3並且者小於5時.沒有可能的方案
            return 0;
        } else if (n == 5) {  //當n==5時只有一種可能
            return 1;
        } else if (map.containsKey(n)) {//若Map中已經存在之前的計算結果，則直接從map中獲取
            return map.get(n);
        } else {  //n>5時，採用遞歸的方式進行計算
            int temp = climbStairs(n - 3, map) + climbStairs(n - 5, map);
            map.put(n, temp);
            return temp;
        }
    }

上述動態規劃在n比價小的時候並不能體現其優勢，但當n較大時，就有可一避免出現多處的重複計算的情況，較少時間複雜度；

拓展思考：

　　變形一：每次能走3階、5階、7階時，有多少種可能？

　　　　思路：F(n)=F(n-3)+F(n-5)+F(n-7)

　　變形二：每次最多走M階，問走到N階有多少種可能？

　　　　思路：F(n)=F(n-1)+F(n-2)+F(n-3)……F(n-m)

程式碼實現　

    public static int countM(int n, int m, Map<Integer, Integer> map) {
        int count = 0;
        if (n == 0) {
            return 1;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        } else if (n >= m) {
            for (int i = 1; i <= m; i++) {
                count += countM(n - i, m, map);
            }
        } else {
            count += countM(n, n, map);
        }
        map.put(n, count);
        return count;
    }

總結：該演算法是對菲波那切數列的應用，一般情況下,一旦能用數列的形式表示某種關係那麼最先想到的就是遞歸。該題的難點是能夠找到遞歸規律以及在遞歸中各種數值的劃分。

參考鏈接：N級台階，一次上1級或2級或3級或M級，總共有多少種走法

Tags: 演算法