【海外エンジニア転職活動】Coding Interview鍛錬: 02.Memoization - フィボナッチ数（Fibonacci numbers）

今回はフィボナッチの問題を違うアプローチで解いていく！

前回の問題点
Time Complexity ＝ O(2N)

再帰の各レベルでの必要な演算量が、nに近づくにつれて指数関数的に増加してしまう！

atsashimipy.hatenablog.com

というのも一度計算したフィボナッチ数も再帰のなかで何度も計算しているから。

なので今回はメモ化（memoization）を使っていこうと思います。
(注意：Memorization(暗記)ではなくMemoization)
ja.wikipedia.org

キャッシュ（Cache）という呼び方の方が馴染みがある方もいるかもしれません。
つまるところ、一度計算したフィボナッチ数を何処かに保存して、何度も計算する手間を省く手法。

では解いていきます！

1. cache と名付けた辞書に一度計算したフィボナッチ数を補完。この時, key=n
2. nがcacheの中に存在する場合は計算せずに、そちらを参照。

class Solution:
    def fib(self, n: int) -> int:
        cache = {}
        
        def recur_fib(n):
            if n == 0:
                cache[n] = 0
                return 0
            elif n == 1:
                cache[n] = 1
                return 1
            
            if n in cache:
                return cache[n]
            else:
                
                cache[n] = recur_fib(n-2) + recur_fib(n-1)
                return cache[n]
            
        return recur_fib(n)

こうするとnまでの各フィボナッチ数の計算は一度のみで、
Time complexityは O(N)

速いぞ！

余談
ちなみにさっき知ったのですが...
pythonの場合、
Built-inデコレータの一つに、@cacheというものがあり、前回使った関数の上にこのようにくっつけると

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

自動的にメモ化して余分な計算を省いてくれるそうです！なんと便利！
詳しくはこちら（バージョン 3.9 で追加）
docs.python.org

まとめ

最後にデコレータの便利さにインパクト持ってかれたが、このメモ化の解き方はいろんなところに応用できそう！

ご意見感想、こんな風にも解けるよ！というアドバイスお待ちしてます！
ありがとうございましたー！