基本情報技術者 予想問題｜A 第18問

解説

正解はウ。動的計画法（DP）は、問題を部分問題に分割し、部分問題の計算結果を表などに保存して再利用することで、同じ計算の繰り返しを避ける手法である。フィボナッチ数列F(n)＝F(n−1)＋F(n−2)を単純な再帰で計算すると、同じF(k)が何度も再計算され計算量が指数的（O(2^n)程度）に膨らむが、求めた値を保存しながら順に積み上げればO(n)で計算できる。これはDPの典型例である。アの順次表示やエの全要素の2倍は単純な反復処理、イの素数判定は割り切れるかを試すだけの処理であり、部分問題の重複がないためDPの利点が生きない。基本情報では「部分問題の結果を記録して再利用する」というDPのキーワードと、メモ化再帰との関係が頻出である。