定義

フィボナッチ数列は、前の2つの数を足して次の数を作る数列です。動的計画法(DP)の最も基本的な例で、計算済みの値を保存して再利用する方法を学べます。

主な特性

• ✓漸化式: fib(n) = fib(n-1) + fib(n-2)
• ✓基底条件: fib(0) = 0, fib(1) = 1
• ✓重複計算の排除: 同じ値を2度計算しない
• ✓ボトムアップアプローチ: 小さい問題から大きい問題へ

時間計算量