問題
動的計画法（DP）の特徴として、最も適切なものはどれか。
選択肢
- 1問題を部分問題に分割し、部分問題の解を記憶（メモ化）して再利用することで、指数時間を多項式時間に短縮する。
- 2貪欲法のように、各段階で局所的に最適な選択を繰り返すことで全体最適解を得る。
- 3問題空間を分枝限定し、解になり得ない領域を早期に切り捨てて探索を高速化する。
- 4モンテカルロ法を用いて確率的に近似解を求める。
正解
1. 問題を部分問題に分割し、部分問題の解を記憶（メモ化）して再利用することで、指数時間を多項式時間に短縮する。
詳しい解説を見る解説を閉じる
解説
動的計画法は、最適性原理に基づき、部分問題の最適解を記憶（メモ化）して再利用する手法。ナップサック問題やフロイド・ワーシャル法、編集距離計算などに用いられる。2は貪欲法、3は分枝限定法、4はモンテカルロ法の説明。
一問一答
全400問を繰り返し学習