問題
動的計画法（DP）が有効に適用できる条件として、最も適切なものはどれか。
選択肢
- 1問題が貪欲に最適解を構成できる
- 2部分問題に分割でき、最適部分構造と部分問題の重複性を持つ
- 3入力データが整列されている
- 4部分問題が互いに独立で重複しない
正解
2. 部分問題に分割でき、最適部分構造と部分問題の重複性を持つ
詳しい解説を見る解説を閉じる
解説
動的計画法は「最適部分構造」と「部分問題の重複」が成立する場合に効果を発揮する。部分問題の解を表に記録（メモ化）することで指数時間から多項式時間に削減できる。
一問一答
全400問を繰り返し学習