動的計画法を考えます。 \(A[n]\) を\(S=n\) のときの答えとすると、

\(A[n]=A[n-3]+A[n-4]+\cdots+A[0]\) や

\(A[n]=A[n-1]+A[n-3]\)

のように立式できます。ただし \(A[0]=1\) とします。

上の遷移式は、総和が \(n-3,n-4,\cdots,0\) ですべての項の値が \(3\) 以上であるような空でもよい数列に、新たに値が \(3,4,\cdots n\) の項を末尾に加える操作に対応しています。

下の遷移式は、\(A[n]=A[n-3]+A[n-4]+\cdots+A[0]\) の \(A[n-4]+\cdots+A[0]\) の部分を \(A[n-1]\) で置き換えることで得られます。

上の遷移式を用いると \(O(S^2)\)、下の遷移式を用いると \(O(S)\) で答えを求めることができます。高速Kitamasa法を用いてさらに高速に計算することもできます。

解答例（C++）