問題
動的計画法（DP）の特徴として最も適切なものはどれか。
選択肢
- 1部分問題の解を保存し、重複計算を避ける
- 2すべての組合せを試す網羅的探索手法である
- 3常に貪欲に局所最適解を選択する
- 4解の存在を確率的に判定する
正解
1. 部分問題の解を保存し、重複計算を避ける
詳しい解説を見る解説を閉じる
解説
動的計画法は、問題を部分問題に分割し、部分問題の解をメモ化（保存）することで重複計算を避ける手法。最短経路問題（ベルマンフォード法）、ナップザック問題、最長共通部分列などに適用される。網羅探索や貪欲法とは異なる。
一問一答
全400問を繰り返し学習