問題
動的計画法（DP）が有効な問題の性質として、当てはまる組合せはどれか。
選択肢
- 1部分構造最適性と部分問題の重なり
- 2無記憶性と離散性
- 3NP 完全性と多項式時間性
- 4貪欲選択性と独立性
正解
1. 部分構造最適性と部分問題の重なり
詳しい解説を見る解説を閉じる
解説
DP の適用条件は (1) 最適部分構造（最適解が部分問題の最適解から構成できる） (2) 部分問題の重なり（同じ部分問題が複数回現れる）の 2 つ。これらが揃えばメモ化やボトムアップ表により指数的計算を多項式時間に削減できる。フィボナッチ数、ナップサック問題、最長共通部分列（LCS）、編集距離が典型例。貪欲法は局所最適が大域最適となる特殊な場合のみ有効で、DP より制約が強い。分割統治法は部分問題の重なりがない（マージソート等）点で DP と区別される。
一問一答
全400問を繰り返し学習