Pythonでメモ化再帰

今日は過去問から。再帰関数で実装しても、入力が大きい数になるとTLEになった。
なので、色々調べていたらメモ化が有効と聞いて試したので、まとめ。

目次

• メモ化とは
• ABC079 B. Lucas Number

メモ化とは

英語では、Memoizationと言うらしい。
一度計算済みの結果を覚えておき、再度呼ばれたら、その度に計算せずとも覚えた内容を返す。
これ、超便利だった。途中経過を覚えておいてくれれば、再帰関数での計算量が減らせる。
動的計画法(DP)でよく使われるらしい。

ポイント

メモ化は、 デコレータ @functools.lru_cacheを使う
使い方は、 from functools import lru_cacheで呼び出してから、
再帰関数の直前に@lru_cache()デコレータを使う

docs.python.org

ABC079 B. Lucas Number

atcoder.jp

https://atcoder.jp/contests/abc079/tasks/abc079_b

リュカ数を求める部分は、普通に再帰関数で実装できる。
サンプルのテストパターンとして、n = 5 と n = 86 が用意されているが、
何もしないと n = 86の時は延々と実行が終わらない...

ACしたコード

# coding:utf-8
from functools import lru_cache


@lru_cache(maxsize=None)
def lucas(num):
    if num == 0:
        return 2
    elif num == 1:
        return 1
    else:
        return lucas(num - 1) + lucas(num - 2)


def main():
    n = int(input())
    print(lucas(n))


if __name__ == "__main__":
    main()