動的計画法（基礎）貰うDP, 配るDP

def fib(n):
    # memo[i]: i番目のフィボナッチ数
    memo = [0 for _ in range(n + 1)]
    # 0番目と1番目のフィボナッチ数は1と決まっているので初期化で設定しておく
    memo[0] = 1
    memo[1] = 1
    for i in range(2, n + 1):
        # (1)
        # i番目のフィボナッチ数はi-1番目のi-2番目のフィボナッチ数の和
        # i番目を求めるためにi-1番目とi-2番目の値を貰っている
        memo[i] = memo[i - 1] + memo[i - 2]

    return memo[n]

def fib(N):
    if N < 2:
        return 1

    # 1つ前（prev）と2つ前（pprev）のフィボナッチ数を保持しておく
    # 最初は1番目の0番目のフィボナッチ数で初期化
    prev, pprev = 1, 1
    # 現在のフィボナッチ数、最初はなんでも良いのでとりあえず-1で初期化しておく
    cur = -1
    for _ in range(2, N + 1):
        # 1つ前と2つ前のフィボナッチ数を合計することで現在のフィボナッチ数を求めている
        cur = prev + pprev
        # 1つ前と2つ前のフィボナッチ数を更新
        prev, pprev = cur, prev

    return cur

def fib(N):
    # memo[i]: i番目のフィボナッチ数
    memo = [0 for _ in range(N + 1)]
    # 0番目のフィボナッチ数は1と決まっているので初期化で設定しておく
    # 1番目のフィボナッチ数はfor文内で0番目と同じ数となるように計算されているので、
    # ここでは何も設定しない
    memo[0] = 1

    for i in range(N):
        # (1)
        # i番目のフィボナッチ数はi+1番目のi+2番目のフィボナッチ数に寄与される
        # この様にi番目の値をi+1番目とi+2番目の数に配っている
        memo[i + 1] += memo[i]
        if i + 2 < N + 1:
            memo[i + 2] += memo[i]

    return memo[N]