\(3^N\) ステップの DP を \(D\) 回繰り返すと計算量は \(O(D 3^N)\) と評価されます。

空でない福袋を \(k\) 個作った状態において、 \(1,2,\ldots ,k\) 個目のグッズがすでに採用されていると仮定しても構いません。今後考えるべきグッズは \(N-k\) 個になるので、次の福袋を作る DP は \(3^{N-k}\) ステップで完了します。

作る福袋の個数が \(D\) 未満である場合の計算結果を利用すると、空の福袋を考慮できます。

ステップ数の合計は \(3^{N}+3^{N-1}+3^{N-2}+\cdots +1\leq \frac{3}{2}\cdot 3^N\) 以下です。計算量は \(O(3^N)\) です。

解答例