【SC試験午前I】動的計画法によるアルゴリズム設計 — アルゴリズムとプログラミング | 情報処理安全確保支援士問題集

問題

動的計画法（Dynamic Programming）に関する記述として、適切なものはどれか。

ア）動的計画法は、問題を部分問題に分割し、それぞれを独立に解いた後、部分問題の解を再利用せずに毎回再計算する手法である。

イ）動的計画法は、部分問題の解を記憶（メモ化）しておき、同じ部分問題を再計算せずに再利用することで効率化を図る手法である。

ウ）動的計画法は、常に貪欲法（グリーディ法）と同じ結果を導き、両者は数学的に等価な手法である。

エ）動的計画法は、部分問題間に重なりがない問題にのみ適用可能であり、重複部分問題を持つ問題には適用できない。

解答・解説を見る

正解： イ）

解説：

ア）動的計画法の本質は、一度計算した部分問題の解を再利用することで計算量を削減する点にあります。「毎回再計算する」のは動的計画法を使わない単純な再帰（分割統治法の一部）に近く、誤りです。
イ）動的計画法は、問題を部分問題に分割し、それぞれの解を配列やテーブルに記憶（メモ化）しておくことで、同じ部分問題を何度も計算し直すことを避け、全体の計算量を削減する手法です。正解です。
ウ）貪欲法は各段階で局所的に最適な選択を積み重ねる手法であり、必ずしも全体最適解を導くとは限りません。動的計画法はより網羅的に部分問題の解を評価するため、両者は等価ではなく、誤りです。
エ）動的計画法が特に有効なのは、まさに「重複する部分問題」を持つ問題（同じ部分問題が繰り返し出現する問題）です。「重複部分問題を持つ問題には適用できない」は動的計画法の適用条件と正反対であり、誤りです。