dynamic programming task / counting problem

Question

I am struggling with a dynamic programming task I cannot solve. I've found in a book a similar problem when you are asked to calculate the number of solutions and it says that this is a counting problem not optimization problem which is obvious. I want an advice how to deal with this kind of tasks and i want to know if there is a general approach to this. I want to know the recursive relation here and which are the subproblems. Here is the problem:

You are given n places to place your cubes. Minimum three consecutive cubes are considered as a figure. Figures are separated by minimum one place. You are asked to calculate all ways you can place the figures on the free places. Here is a solution for n = 7. Blue squares represent free places to place a cube and red ones are the cubes. Number of ways is equal to 17.

Answer 1

@saeedn almost had it, but his recursive formula is not quite correct, as it has some missing cases and some double countings.

Let's examine the possibilities for the first place, either it's a space (single space), or there is a figure there. The length of the figure could be 3,4,...,n-1,n.
If it is less then n, we also need to add 'padding' before the next figure (to avoid double countings), so if we have a figure of 3 cubes, it has f(n-4) different possibilities (with the first 3 cells being cubes). An exception is for a figure of n nodes, because we cannot add a 'padding' after it.

Another possibility is a single space, and if there will be more spaces, the recursion will take care of it later on.

This gives us the following recursive formula:

f(0) = f(1) = f(2) = 1 (base)
f(n) = f(n-4) + f(n-5) + ... + f(1) + f(0) +   f(0)      + f(n-1)
         ^        ^             ^       ^       ^             ^
         3        4             n-2     n-1      n           space
       cubes    cubes          cubes    cubes   cubes
         +         +             +       +        +
        space    space         space    space   space   

So, if we imply this formula to a DP algorithm, we'll get:

arr[n+1] = [0,0,...,0]
arr[0] = arr[1] = arr[2] = 1
for (int i = 3; i < n+1; i++) 
   for (int j = 0; j <= i - 4; j++)  //f(n-4) + f(n-5) + ... + f(1) + f(0)
      arr[i] += arr[j]
   arr[i] += arr[0] // extra one f(0) for a shape with i cubes
   arr[i] += arr[i-1] // space
return arr[n]