時間ができたので100周遅れでAtCoderに入門するため、動的計画法（以下DP）に取り組みはじめました。

TL;DR

プログラミングコンテストにおける動的計画法のフィボナッチ数列の部分をPythonで実装しただけです。

DP

同じ探索を2度しないようにすること
一度計算したら結果を保存して使い回す

フィボナッチ数列

「フィボナッチ数列」とは，「前の２つの数を加えると次の数になる」という数列です。
ただし，１番目と２番目の数は両方とも１です。

第0～21項の値は次の通り：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …


> - フィボナッチ数列（フィボナッチすうれつ、（英: Fibonacci sequence） (Fn) は、次の漸化式で定義される：

> ```math
F0 = 0\\
F1 = 1\\
F_{n+2} = F_n + F_{n+1}\,(n ≥ 0)\\

Studyplus
Wikipedia

処理時間計測

処理時間を計測する際、頻繁に使用している推し関数があるので紹介します！
kaggleマスターのアライさんが紹介していたtimer関数をシンプルにしました
（これを知れただけでもkaggleやっててよかった...）

import time
from contextlib import contextmanager


@contextmanager
def timer():
    t0 = time.time()
    msg = "start"
    print(msg)
    yield
    msg = f"done in {time.time() - t0:.2f} s"
    print(msg)

Kaggleコード遺産

本題

普通にフィボナッチ数を計算する

def fib(n: int):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

メモ探索（再帰関数のメモ化）

def fib_memo(n: int):
    global done
    global memo
    if n == 0: return 0
    if n == 1: return 1

    if done[n]:
        return memo[n]

    done[n] = True
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

動的計画法（漸化式＋ループ）

def fib_loop(n: int):
    global memo
    memo[0] = 0
    memo[1] = 1

    for i in range(2, n+1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

実行

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("method", help="Select to solve with which fibonacci method")
    parser.add_argument("max_num", help="Set max number")
    args = parser.parse_args()

    n = int(args.max_num)
    done = [False] * (n + 1)
    memo = [0] * (n + 1)
    with timer():
        print(eval(args.method)(n))

コマンド

python fibonacci.py fib_memo 1000

処理速度

上記の3つでは動的計画法が最も早く、次にメモ探索、最も遅いのは普通にフィボナッチ数を計算する場合でした。

プログラミングコンテストにおける動的計画法に記載があるように計算量が指数時間かかるか擬多項式時間かかるかの違いのようです。

動的計画法 < メモ探索 <<<<<<<<<<<<<<<<<< 普通にフィボナッチ数

n = 30000の場合
- 動的計画法： 0.04 s
- メモ探索： 0.06 s
- 普通にフィボナッチ：　終わらない(n=100でもめっちゃ時間かかる）

詳細はGithubを参照くださいませ