問題
動的計画法の特徴として、正しいものはどれか。
選択肢
- 1問題を独立した部分問題に分割し再帰的に解く
- 2部分問題の解を保存し再利用することで重複計算を避ける
- 3すべての可能性を試して最適解を求める
- 4貪欲に局所最適を選び続ける
正解
2. 部分問題の解を保存し再利用することで重複計算を避ける
詳しい解説を見る解説を閉じる
解説
動的計画法（DP: Dynamic Programming）は、問題を部分問題に分割し、部分問題の解をメモ化（保存）して再利用することで重複計算を避け効率化する手法です。最適部分構造と重複部分問題の2性質を持つ問題に有効で、ナップサック問題、最長共通部分列、最短経路問題などに適用されます。分割統治法と異なり、部分問題が重複する点が特徴です。
一問一答
全400問を繰り返し学習