I was trying to solve this problem from APIO 2016 (link here) and I found that it is very similar to the second problem on Topcoder SRM 728 Medium (link here)

Namely, in the topcoder we only want to count the valid sequences of length $$$N$$$, but for the APIO version we want to count all valid sequences of length from $$$1$$$ to $$$N$$$ instead of just the whole array.

I have read the tutorial for the Topcoder version and I understand how it works, however I cannot understand how to make this DP solution work for each subset of the array instead of working for the whole array.

Here is link for the tutorial for the Topcoder problem