以下の \(2\) つをキーとして、最初の項から順番に決めていく動的計画法をします。

• 何項決めたか
• 今までに使った要素の集合

ただし、今までに使った要素の集合を愚直に管理すると \(2^n\) 通りありうるため、工夫する必要があります。

最初の \(i\) 項が決まっているとき、以下を満たしていないと、残りをどう決めても条件を満たしません。

• \(i-d\) 以下の要素はすべて使用済み
• \(i+d+2\) 以上の要素はどれも使われていない

よって、各 \(i\) に対して、 \(i-d+1\) 以上 \(i+d+1\) 以下の数のみについて、すでに使用済みかどうかを持てば十分です。 このような集合は \(2^{2d+1}\) 通りしかないため、これで動的計画法のテーブルのサイズは \(O(4^dn)\) となります。 それぞれの状態に対して遷移が \(d\) 通りあるため、計算量は \(O(4^ddn)\) です。

C++による実装例