[PYTHON] I tried to study DP with Fibonacci sequence

Since I had time, I started working on dynamic programming (DP) in order to get started with AtCoder 100 laps later.

TL;DR I just implemented the Fibonacci sequence part of Dynamic Programming in Programming Contest in Python.

DP Don't do the same search twice Once calculated, save the result and reuse it

Fibonacci sequence

The "Fibonacci sequence" is a sequence that "adds the previous two numbers to get the next number". However, the first and second numbers are both 1.

--The values in items 0 to 21 are as follows:

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

 > --The Fibonacci sequence (Fn) is defined by the following recurrence formula:

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

Studyplus Wikipedia

Processing time measurement

I will introduce a guess function that I often use when measuring processing time! Simplified the timer function introduced by kaggle master Arai (I'm glad I did kaggle just to know this ...)

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 Code Heritage

Main subject

Calculate Fibonacci numbers normally

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

Memo search (memoization of recursive function)

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]

Dynamic programming (recurrence formula + loop)

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]

Run

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))

command

python fibonacci.py fib_memo 1000

processing speed

Of the above three, dynamic programming was the fastest, then memo search, and the slowest was when calculating the Fibonacci number normally.

It seems that the amount of calculation takes exponential time or pseudo-polynomial time as described in Dynamic programming in programming contest.

Dynamic programming<Memo search<<<<<<<<<<<<<<<<<<Fibonacci number normally

--When n = 30000 --Dynamic programming: 0.04 s --Memo search: 0.06 s --Normally Fibonacci: It doesn't end (it takes a lot of time even with n = 100)

Please refer to Github for details