Algorithm to 'count the number of ways a floor of size 5*N can be filled with tiles of sizes 1*5 and 2*5'

Question

Here is the part of the question with copied for ref:

*You are given a floor of size 5xN. You have tiles of 2 different sizes: 1x5 and 2x5. Of course, you can rotate the tiles to get 2 more tile sizes: 5x1 and 5x2. You have to do the flooring using these tiles in the following way:

1. Floor space should be completely covered by tiles.
2. You cannot break tiles, ie, you have to use a tile entirely or not at all.
3. Any tile should not extend beyond the floor space.
4. Tiles should be placed parallel to the floor boundaries.

Your task is to find the number of ways in which you can lay the tiles on the floor*

Can I get some help with the approach. Thanks in advance.

Edit: I understand now when we have to count the ways to fill floor of size 5*N with tiles of size 5*1. With dp we can achieve it like this dp[1]=1,dp[2]=1,dp[3]=1,dp[4]=1,dp[5]=2 and dp[n]=dp[n-1]+dp[n-5] http://www.geeksforgeeks.org/count-number-ways-tile-floor-size-n-x-m-using-1-x-m-size-tiles/

But I don't understand how to formulate dp[n] when there are more than one tile of different sizes. You are given a floor of size 5xN. You have tiles of 2 different sizes: 1x5 and 2x5.

Answer 1

This answer from Math.SE helped me formulate the recurrence. Posting my solution, for someone may find it useful. There are total 10 ways first column of 5n can be tiled by dominos of size 15 and 2*5 shown and named in picture below: We'll count the number with each kind of beginning configuration and add the results up to get f(n).

Any 5*(n-1) can extend to give 5n tiling and there are no other way to get a "type a" 5n tiling. So, there are f(n-1) "type a" tilings. Similarly, there are f(n-2) "type b" 5*n tiling. Similarly type c to j all have f(n-5) tiling. That makes:

f(n)=f(a)+f(b)+f(c)+f(d)+f(e)+f(f)+f(g)+f(h)+f(i)+f(j)
f(n)=f(a)+f(b)+8*f(c)
f(n)=f(n-1)+f(n-2)+ 8*f(n-5)

Below is the c++ code used and tested:

int dp[1000000]={0};
int count(int n){
    if(n<0){
        return 0;
    }
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    if(dp[n]>0){
        return dp[n];
    }
    
    dp[n] = count(n-1)+count(n-2)+8*count(n-5);
    
    return dp[n];    
}