最適部分構造

最適化問題の族 $\{P_s\}_{s \in S}$ があり、$P_s$ の最適値を $V(s)$ とします。各 $s \in S$ に対して依存先 $D(s) = (s_1, \ldots, s_k)$ と関数 $g_s$ が存在して

が成り立ち、かつ依存グラフが DAG になるとき、この問題族は最適部分構造をもつといいます。