問題
次のアルゴリズムで、動的計画法を使う問題として最も適切なものはどれか。
選択肢
- 1ア 配列の先頭から順に値を表示する
- 2イ 与えられた整数が素数か判定する
- 3ウ フィボナッチ数列のn番目を効率的に計算する
- 4エ 配列の要素をすべて2倍にする
解答と解説を見る
正解
3. ウ フィボナッチ数列のn番目を効率的に計算する
解説
動的計画法（DP）は、部分問題の結果を保存して再計算を避ける手法です。フィボナッチ数列は再帰的に定義されますが、同じ部分問題が何度も現れるため、DPで効率化できます（O(2^n)→O(n)）。