部分問題族と依存グラフ

有限集合 $S$ と、各 $s \in S$ に対して定まる値 $V(s)$ の組が次の 3 条件を満たすとき、これを部分問題族と呼ぶことにします。

1. 各 $s \in S$ に、$S$ の元からなる有限列 $D(s) = (s_1, \ldots, s_{k_s})$ が定まっている。これを $s$ の依存先と呼びます。
2. 各 $s \in S$ に関数 $g_s$ が定まっていて、$V(s) = g_s\bigl(V(s_1), \ldots, V(s_{k_s})\bigr)$ が成り立つ。
3. 有向グラフ $G = (S, E)$、$E = \bigl\{ (s', s) : s \in S,\ s' \in D(s) \bigr\}$ が閉路をもたない（DAG である）。

$k_s = 0$ である $s$、すなわち依存先をもたない部分問題を基底と呼びます。基底では $V(s) = g_s()$ は定数として直接与えられます。