CareerCup

This can be solved with dynamic programming first we need to find the recurrence formula
There are just to way to put a single sheet is vertical or horizontal. See the wall as the row so if you put horizontal you occupy 4 positions and below of that you only can put 3 more horizontals sheets no more. If you put vertical just cover the whole column.
So let's define F[0] as the empty wall
F[0] = 1;
F[i] = put vertical + put horizontal
vertical is F[i-1]
horizontal is F[i-4]
note horizontals can be fit only on wall with 4 or more columns
This is O(N) solutions
But using matrices you can find the Nth value on O(log N)

Imagine the 4*n grid positioned with the 4 units going horizontally and n units going vertically. Without loss of generality, we start filling from the top left, since we will have to fill that space eventually anyway and the order of placing blocks doesn't matter. We have a choice: we can place a wall vertically from the top left corner (4 down, 1 across) or horizontally (4 across, 1 down). If we place a block vertically, the rest of the 3 horizontal spaces will need to be filled in the same way, vertically, since no blocks positioned horizontally could ever fit there. After that's done, there will be a 4*(n-4) grid left to fill. You also have the option of placing the 4 side horizontally and the 1 side vertically, leaving behind a 4*(n-1) grid.

All of this means that if f(n) is the number of ways to arrange a 4*n grid, then f(n) = f(n-4) + f(n-1), using f(0) = 1 and f(any negative number) = 0 as base cases. You can then compute f(n) using a similar approach to how Fibonacci numbers are computed. You have the option between 3 standard solutions that are used for Fibonacci:

1) The naive O(n) loop that calculates f(1), then f(2), then f(3), and so on. Since f(n) depends only on smaller values of the function, you will always have all the values you need.

2) A recursive solution that caches previously computed values -- the caching (essentially, dynamic programming) is necessary to avoid recomputing a lot of cases, just like in Fibonacci.

3) A solution based on representing the linear recurrence as a matrix. This allows the answer to be computed in O(log n) time. The linear recurrence is f(n) = f(n-4) + f(n-1) instead of the f(n) = f(n-2) + f(n-1) seen with Fibonacci, but other than adjusting the matrix, this is the same solution as finding the n-th Fibonacci number in log time.