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

Recommended Posts

I tried to study DP with Fibonacci sequence
I tried recursion with Python ② (Fibonacci sequence)
I tried to find the average of the sequence with TensorFlow
I tried to implement Autoencoder with TensorFlow
I tried to visualize AutoEncoder with TensorFlow
I tried to get started with Hy
I tried to implement CVAE with PyTorch
I tried to solve TSP with QAOA
I tried to predict next year with AI
I tried to detect Mario with pytorch + yolov3
I tried to implement reading Dataset with PyTorch
I tried to use lightGBM, xgboost with Boruta
I tried to learn logical operations with TF Learn
I tried to move GAN (mnist) with keras
I tried to save the data with discord
I tried to detect motion quickly with OpenCV
I tried to integrate with Keras in TFv1.1
I tried to get CloudWatch data with Python
I tried to output LLVM IR with Python
I tried to debug.
I tried to detect an object with M2Det!
I tried to automate sushi making with python
I tried to predict Titanic survival with PyCaret
I tried to paste
I tried to operate Linux with Discord Bot
I tried to start Jupyter with Amazon lightsail
I tried to judge Tsundere with Naive Bayes
I tried to move machine learning (ObjectDetection) with TouchDesigner
I tried to extract features with SIFT of OpenCV
I tried to move Faster R-CNN quickly with pytorch
I tried to read and save automatically with VOICEROID2 2
I tried to implement and learn DCGAN with PyTorch
I tried to implement Minesweeper on terminal with python
I tried to get started with blender python script_Part 01
I tried to touch the CSV file with Python
I tried to draw a route map with Python
I tried to solve the soma cube with python
I tried to automatically read and save with VOICEROID2
I tried to get started with blender python script_Part 02
I tried to generate ObjectId (primary key) with pymongo
I tried to implement an artificial perceptron with python
I tried to build ML Pipeline with Cloud Composer
I tried to uncover our darkness with Chatwork API
I tried to automatically generate a password with Python3
[Introduction to Pytorch] I tried categorizing Cifar10 with VGG16 ♬
I tried to solve the problem with Python Vol.1
I tried to analyze J League data with Python
I tried to implement Grad-CAM with keras and tensorflow
I tried to make an OCR application with PySimpleGUI
I tried to implement SSD with PyTorch now (Dataset)
I tried to interpolate Mask R-CNN with Optical Flow
I tried to step through Bayesian optimization. (With examples)
I tried to find an alternating series with tensorflow
I tried to implement automatic proof of sequence calculation
[Introduction to AWS] I tried playing with voice-text conversion ♪
I tried to solve AOJ's number theory with Python
I tried fp-growth with python
I tried scraping with Python
I tried Learning-to-Rank with Elasticsearch!
I tried to organize SVM.
I tried clustering with PyCaret