Number of ways to fill or construct wall of N X 4 with 4 X 1 bricks

Let me clarify the question, as shown in figure 1 X 4 brick can be used as 4 X 1 brick also, and we have a wall of N X 4 or 4 X N unit.

brick_wallTo fill this wall with given brick, we can either put brick standing, or horizontally. Going further, we will take above wall as input and not as N X 4, although solution remains the same
Now, if I have a wall with N =1, i.e. 4 X 1 wall, there is only one possible way I can fill that way, and that is to lay brick horizontally on the wall. Solutions = 1
What if N = 2, i.e. wall as 4 X 2, then I can put two bricks horizontally, that is the only way, I can put brick in vertical as it will go our of the wall. Solutions = 1
Take N  =3, i.e. wall with 4 X 3, only way we can fill the wall is to put three bricks horizontally, can’t use vertical brick. So, solutions = 1
What if N =4, wall with 4 X 4 dimensions, in this scenarios, there are two cases, we put four bricks horizontally or we put four bricks vertically, so the number of solution for 4 X 4 is 2.

Figure explains what I wrote above

brick_wall1If we take number of solutions as f(n) then f(n) for values 1,2 and 3 is as follows.

f(1) =1, f(2)=1, f(3)=1

We have two choices for each brick for wall of size greater than 4 X 3.  Either we keep brick vertically or we keep brick horizontally. If we keep brick vertically, we cover four units out of N units height of wall with each brick, require four vertical bricks to cover horizontally, so problem reduces to N-4 units. If we keep brick horizontally, then it covers only 1 unit height of wall, hence we need to cover N-1 units of height further.
So, for n we have relationship as

f(n) = f(n-1)  + f(n-4)

Now we have recurrence relation and based condition, it should be easy to implement it with recursion.

However, if we look at the solution closely, we can find that many of the sub problems are being solved again and again, that means sub problems are overlapping. Remember Fibonacci series? So typical case of dynamic programming. Below code provides solution with Dynamic programming.

This is the simple implementation in dynamic programming, to solve the problem of finding number of ways in which N X 4 wall can be constructed or mapped with 4 X 1 or 1 X 4 bricks.
If you find some issue in understanding it, please leave a comment, I will elaborate it more. Otherwise you can share and spread the knowledge.