動的計画法:フィボナッチ数

2025-04-05 · algorithms, python

はじめに

動的計画法(Dynamic Programming)は、問題をより小さな部分問題に分割して解く効率的なアルゴリズム設計手法です。 部分問題の結果を保存しておくことで、無駄な再計算を避けます。

フィボナッチ数の素朴な再帰アルゴリズム

def fib_naive(n):
    if n <= 2:
        return 1
    else:
        return fib_naive(n - 1) + fib_naive(n - 2)

メモ化アルゴリズム

def fib_memo(n, memo=None):
    if memo is None: memo = {}
    if n in memo: return memo[n]

    if n <= 2: result = 1
    else: result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)

    memo[n] = result
    return result

ボトムアップDP | 時間: O(n)、空間: O(1)

def fib_bottom_up_O1(n):
    if n <= 2: return 1
    prev, curr = 1, 1
    for k in range(2, n):
        prev, curr = curr, prev + curr
    return curr

ボトムアップDP | 時間: O(n)、空間: O(n)

def fib_bottom_up_On(n):
    if n == 1: return [1]
    if n == 2: return [1, 1]

    fib = [0] * n
    fib[0], fib[1] = 1, 1

    for k in range(2, n):
        fib[k] = fib[k - 1] + fib[k - 2]

    return fib