【遞歸】(三) (Memorization) 記憶化技術

目錄

一、遞歸中的重複計算

二、斐波那契數

2.1 題目要求

2.2 解決過程

三、爬樓梯

3.1 題目要求

3.2 解決過程

四、爬樓梯多解

一、遞歸中的重複計算

# Python implementation
def fibonacci(n):
    """
    :type n: int
    :rtype: int
    """
    if n < 2:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)
           

def fib(self, N):
    """
    :type N: int
    :rtype: int
    """
    cache = {}
    def recur_fib(N):
        if N in cache:
            return cache[N]
        if N < 2:
            result = N
        else:
            result = recur_fib(N-1) + recur_fib(N-2)

        # put result in cache for later reference.
        cache[N] = result
        return result

    return recur_fib(N)
           

參考文獻：https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memorization/1211/

二、斐波那契數

2.1 題目要求

2.2 解決過程

個人實作

法一：無記憶遞歸。

2020/07/19 - 18.27% (800ms) - 最簡單但低效的方法 

class Solution:
    def fib(self, N: int) -> int:
        if N == 1:
            return 1
        if N == 0:
            return 0
        return self.fib(N-1) + self.fib(N-2)
           

法二：有記憶遞歸。使用字典 memory 來記憶計算過的結果，避免重複備援的計算。

2020/07/19 - 53.74% (44ms) - 性能顯著提升，但由于實作存在問題，未能發揮最佳效果 (對比官方法三)

class Solution:
    def __init__(self):
        self.memory = {0: 0, 1: 1}  # 計算記錄, 但其實這種方式效率并不高, 詳見官方法三

    def fib(self, N: int) -> int:
        if N in self.memory:
            return self.memory[N]
        else:
            self.memory[N] = self.fib(N-1) + self.fib(N-2)  # 記憶
        
        return self.memory[N]
           

官方實作與說明

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib(N-1) + self.fib(N-2)
           

2020/07/19 - 12.98% (800ms)

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.memoize(N)

    def memoize(self, N: int) -> {}:
        cache = {0: 0, 1: 1}
        # Since range is exclusive and we want to include N, we need to put N+1.
        for i in range(2, N+1):
            cache[i] = cache[i-1] + cache[i-2]
        return cache[N]
           

2020/07/19 - 73.37% (40ms)

## 這比個人實作二還要好, 注意對比 cache 的來源與差異
class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        self.cache = {0: 0, 1: 1}  # 比放在資料成員的個人實作法二要好
        return self.memoize(N)

    def memoize(self, N: int) -> {}:
        if N in self.cache:
            return self.cache[N]
        self.cache[N] = self.memoize(N-1) + self.memoize(N-2)
        return self.memoize(N)
           

 2020/07/19 - 99.21% (28ms) - 接近最佳 (注意，實作時将遞歸體封裝在另一個成員函數中了)

class Solution:
    def fib(self, N: int) -> int:
        if (N <= 1):
            return N
        if (N == 2):
            return 1

        current = 0
        prev1 = 1
        prev2 = 1

        # Since range is exclusive and we want to include N, we need to put N+1.
        for i in range(3, N+1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        return current
           

2020/07/19 - 53.74% (44ms)

## 這就牛掰了, 開始使用數學思想了, 是以更有些費解, 但很值得學習！
class Solution:
    def fib(self, N: int) -> int:
        if (N <= 1):
            return N

        A = [[1, 1], [1, 0]]  # 中間幂矩陣的基數矩陣
        self.matrix_power(A, N-1)  # 使用遞歸函數 matrixPower 計算給定矩陣 A 的幂。幂為 N-1
        return A[0][0]

    def matrix_power(self, A: list, N: int):
        if (N <= 1):
            return A

        self.matrix_power(A, N//2)  # matrixPower 函數将對 N/2 個斐波那契數進行操作！
        self.multiply(A, A)  # 矩陣乘法
        B = [[1, 1], [1, 0]]

        if (N%2 != 0):  # 奇數次補乘 如 3, 因為對于偶數次幂 N=2x 而奇數次幂 N=2x+1
            self.multiply(A, B)

    def multiply(self, A: list, B: list):
        x = A[0][0] * B[0][0] + A[0][1] * B[1][0]
        y = A[0][0] * B[0][1] + A[0][1] * B[1][1]
        z = A[1][0] * B[0][0] + A[1][1] * B[1][0]
        w = A[1][0] * B[0][1] + A[1][1] * B[1][1]

        A[0][0] = x
        A[0][1] = y
        A[1][0] = z
        A[1][1] = w
           

2020/07/19 - 96.20% (32ms) - 接近最佳，強大的 O(logn) 複雜度

# 這是什麼神仙操作 ...
class Solution:
  def fib(self, N):
  	golden_ratio = (1 + 5 ** 0.5) / 2
  	return int((golden_ratio ** N + 1) / 5 ** 0.5)
           

2020/07/19 - 96.20% (32ms) - 最佳，驚人的 O(1) 複雜度

其他實作 

若此時要求 通過遞歸傳回斐波那契數列的前 N 項，則出了有記憶遞歸，還可以：

LRU cache 緩存裝飾器 (decorator)：根據參數緩存每次函數調用結果，對于相同參數的，無需重新函數計算，直接傳回之前緩存的傳回值。緩存資料是并不一定快，要綜合考量緩存的代價以及緩存的時效大小。經典例子是改造 fib 序列。

• 若 maxsize=None，則禁用 LRU 功能，且緩存可無限制增長；當 maxsize=2^x 時，LRU 功能執行得最好；
• 若 typed=True，則不同類型的函數參數将單獨緩存。例如，f(2) 和 f(2.0) 将被視為具有不同結果的不同調用；
• 緩存是有記憶體存儲空間限制的；

2020/07/20 - 73.37% (40ms) - 不錯

from functools import lru_cache
class Solution:
    @lru_cache
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib(N-1) + self.fib(N-2)
           

參考文獻

https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memorization/1212/

https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode/

https://www.jianshu.com/p/1e8318220bba

https://mp.weixin.qq.com/s?__biz=MzU0MDczMDUzMQ==&mid=2247484006&idx=1&sn=04d79d1ac51eabec5dfe2f3f444abff6&chksm=fb35f7aacc427ebccfaeb9faf55a9240d5e0dd35a8d4c1b0eff37637ef0243b30ccbe4b5da7d&scene=158#rd

三、爬樓梯

3.1 題目要求

3.2 解決過程

個人實作

法一：數學法 - 組合。通過排列組合中的 組合公式，累計 1 和 2 元素的各組合數。對本題而言，不論是爬一大步還是爬一小步，隻要是爬 1 階，就都是 無差别的，2 階同理。故此處使用組合而非排列，通過 m！消除重複的排列情況。空間複雜度 O(1)，時間複雜度 O(n^2) ？

此外，該實作的高效性得益于 math.factorial() 函數的底層優化，否則手寫階乘函數效率将會極其低下。

2020/07/21 - 98.95% (28ms) - 數學法往往效果很好

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 4:
            return n
        
        one = n                     # 初始化 n 個 1
        two = 0                     # 初始化 0 個 2
        limit = n // 2              # 2 個數上限
        count = 0                   # 種類計數
        while two <= limit:
            # 資料準備
            summ = one + two        # n
            minn = min(one, two)    # m
            diff = summ - minn      # n-m
            # 組合 C^m_n = A^m_n / m! = n! / (n-m)! / m!
            count += (math.factorial(summ) // math.factorial(diff)) // math.factorial(minn)  
            # 更新組合元素 
            one -= 2                # 減少 2 個 1
            two += 1                # 增加 1 個 2
        return count
           

法二：數學法 - 找規律。根據測試用例及其結果，可以發現如下數列規律：

• 輸入：1、2、3、4、5、6、7 ...
• 輸出：1、2、3、5、8、13、21 ...

即從第三個數字開始，每個數字都是前兩個數字之和，這就是 斐波那契數列 的性質，是以可以直接使用斐波那契數的解法來處理本題。

2020/07/22 - 15.86% (48ms) - 實作相對低效

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 4:
            return n
        self.cache = {1: 1, 2: 2, 3: 3}
        return self.fib(n)
    
    def fib(self, m):
        if m in self.cache:
            return self.cache[m]
        self.cache[m] = self.fib(m-1) + self.fib(m-2)
        return self.cache[m]
           

法三：數學法 - 黃金分割比。修改自上一題 —— 斐波那契數的官方實作六。空間複雜度 O(1)，時間複雜度 O(1)。

2020/07/22 - 85.31% (36ms) - 強大

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 4:
            return n
        golden_ratio = (1 + 5 ** 0.5) / 2
        return int((golden_ratio ** (n+1) + 1) / 5 ** 0.5)  # n 改成 n+1
           

官方實作與說明

個人了解：因為第 x-1 階與第 x-2 階有别，故各自的攀爬方案 f(x-1) 與 f(x-2) 一定完全不同。而要想一次爬到第 x 階，隻有兩種初始情況：從第 x-1 階爬 1 步 or 從第 x-2 階爬 2 步。故第 x 階的攀爬方案滿足 f(x) = f(x-1) + f(x-2)。

// C++ implementation
class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};
           

// JAVA implementation
class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}
           

// JAVA implementation
public class Solution {
   public int climbStairs(int n) {
       int[][] q = {{1, 1}, {1, 0}};
       int[][] res = pow(q, n);
       return res[0][0];
   }
   public int[][] pow(int[][] a, int n) {
       int[][] ret = {{1, 0}, {0, 1}};
       while (n > 0) {
           if ((n & 1) == 1) {
               ret = multiply(ret, a);
           }
           n >>= 1;
           a = multiply(a, a);
       }
       return ret;
   }
   public int[][] multiply(int[][] a, int[][] b) {
       int[][] c = new int[2][2];
       for (int i = 0; i < 2; i++) {
           for (int j = 0; j < 2; j++) {
               c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
           }
       }
       return c;
   }
}
           

// JAVA implementation
public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int)(fibn / sqrt5);
    }
}
           

# Python implementation
class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 4:
            return n
        sqrt5 = math.sqrt(5)
        fibn = math.pow((1+sqrt5) / 2, n+1) - math.pow((1-sqrt5) / 2, n+1)
        return int(fibn / sqrt5)
           

參考文獻

https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memorization/1213/

https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

四、爬樓梯

// JAVA implementation
public class Solution {
    public int climbStairs(int n) {
        climb_Stairs(0, n);
    }
    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
}
           

# Python implementation
class Solution:
    def climbStairs(self, n: int) -> int:
        return self.climb_Stairs(0, n)

    def climb_Stairs(self, i, n):
        if i > n:
            return 0
        if i == n:
            return 1
        return self.climb_Stairs(i+1, n) + self.climb_Stairs(i+2, n)
           

// JAVA implementation
public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}
           

# Python implementation
class Solution:
    def climbStairs(self, n: int) -> int:
        memo = [0 for _ in range(n+1)]  # memo = [0] * (n+1)
        return self.climb_Stairs(0, n, memo)

    def climb_Stairs(self, i, n, memo):
        if i > n:
            return 0
        if i == n:
            return 1
        if memo[i] > 0:
            return memo[i]
        memo[i] = self.climb_Stairs(i+1, n, memo) + self.climb_Stairs(i+2, n, memo)
        return memo[i]
           

// JAVA implementation
public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
           

// JAVA implementation
public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}
           

// JAVA implementation
 public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}
           

// JAVA implementation
public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}
           

 參考文獻：https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memorization/1214/#3