https://www.youtube.com/watch?v=5dRGRueKU3M

principle-of-optimality.py

import time


def recursive_fib_memo(val, memo):
    if val <= 1:
        return val
    elif val not in memo:
        memo[val] = recursive_fib_memo(val - 2, memo) + recursive_fib_memo(val - 1, memo)
    return memo[val]


def recursive_fib(val):
    if val <= 1:
        return val
    else:
        return recursive_fib(val - 2) + recursive_fib(val - 1)


def tabulation_fib(val):
    if val <= 1:
        return val
    tab = {0: 0, 1: 1}

    for i in range(2, val + 1, 1):
        tab[i] = tab[i - 2] + tab[i - 1]

    return tab[val]


def dp_fib(val):
    if val <= 1:
        return val
    p1 = 0
    p2 = 1
    curr = None
    for _ in range(2, val + 1, 1):
        curr = p1 + p2
        p1 = p2
        p2 = curr
    return curr


def final_time(init): return time.perf_counter_ns() - init


def main(val):

    ns_memo = time.perf_counter_ns()
    print(f"\nrecursive_fib_memo : {recursive_fib_memo(val, {})} ")
    print(f"recursive_fib_memo : {final_time(ns_memo)} ns")

    ns_tab = time.perf_counter_ns()
    print(f"\ntabulation_fib     : {tabulation_fib(val)}")
    print(f"tabulation_fib     : {final_time(ns_tab)} ns")

    ns_dp = time.perf_counter_ns()
    print(f"\ndp_fib             : {dp_fib(val)}")
    print(f"dp_fib             : {final_time(ns_dp)} ns")

    ns_rec = time.perf_counter_ns()
    print(f"\nrecursive_fib      : {recursive_fib(val)} ")
    print(f"recursive_fib      : {final_time(ns_rec)} ns]")


if __name__ == '__main__':
    for i in range(1, 31):
        print(f"\n[Running with '{i}'")
        main(i)