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

解説

動的計画法（DP）は、問題をより小さな部分問題に分解し、部分問題の解を表（メモ）に保存して再利用することで、同じ計算の繰返し（重複計算）を避けて効率化する手法である。したがって、部分問題に分解でき、かつ同じ部分問題が繰り返し現れる構造を持つ問題に有効であり、アが正解である。例えばフィボナッチ数列は、単純な再帰では計算量が指数的に増えるが、計算結果を保存するDPならO(n)で求められる。ナップサック問題や最短経路問題も代表的な適用例である。イのソート済みデータという前提は二分探索などの条件であり、ウの乱数生成やエの並列計算の要否はDPの適用条件と無関係である。基本情報技術者試験では、「部分問題への分解」「結果の保存（メモ化）」というDPのキーワードと適用例の対応が頻出ポイントである。