以下のような動的計画法を考えます。

\(\mathrm{DP}_S (S\) は\(\{1, 2, 3, \dots, N\}\) の部分集合\(): a\) の先頭 \(|S|\) 要素まで決めていて、その \(|S|\) 要素で使った数の集合がちょうど \(S\) に一致し、\(X_i \le |S|\) であるような条件は全て満たしているような場合の数

ある \(\mathrm{DP}_S\) から、\(a\) の \(|S| + 1\) 番目の要素を \(x\) に決めて \(\mathrm{DP}_{S \cup \{x\}}\) に遷移することを考えます。この際遷移できる条件は以下の通りです。

• \(x \notin S\)
• \(X_i = |S \cup \{x\}|\) であるような \(i\) について \(S \cup \{x\}\) に含まれる \(Y_i\) 以下の数は \(Z_i\) 個以下

\(\mathrm{DP}_{\{1, 2, 3, \dots, N\}}\) が問題の答えとなります。
よって 状態数が \(2^N\)、遷移が \(1\) つの状態あたり \(O(N)\) で、全体として \(O(2^N N)\) で解けます。

実装の際、\(S\) を整数 \(\displaystyle \sum_{i \in S} 2^{(i - 1)}\) に対応させると配列の添字として使うことができます。ほとんどのプログラミング言語において bit 演算子を使うことで \(S\) に対応する整数から \(S \cup \{x\}\) に対応する整数を簡単に計算することができるため、実装が簡潔になります。
このような実装方法が一般的なことから、上記のような集合を添字に持つ動的計画法は一般に bitDP と呼ばれています。