Consider Dynamic Programming. Let \(A[n]\) be the answer for \(S=n\). Then one can obtain

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

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

Here, we define \(A[0] = 1\).

The former transition formula corresponds to the operation of adding a term \(3,4,\cdots n\) to a (possibly empty) sequence whose sum is \(n-3,n-4,\cdots,0\) and each of whose element is greater than or equal to \(3\).

The latter transition formula can be obtained by replacing \(A[n-4]+\cdots+A[0]\) with \(A[n-1]\) in \(A[n]=A[n-3]+A[n-4]+\cdots+A[0]\).

The answer can be found in a total of \(O(S^2)\) time with the former transition formula, or \(O(S)\) time with the latter transition formula. It can be optimized even more by using a technique of handling linear recurrence formula, which is called “Fast Kitamasa method” in Japanese.

解答例（C++）