# Find number of ways to fill a N x 4 matrix with 1 x 4 tiles

Given a n x 4 matrix where n is a positive number, find number of ways to fill the matrix with 1 x 4 tiles.

For example, there are 3 ways to place `1 x 4` tiles in a `5 x 4` matrix –

1. Place all 5 tiles horizontally.

2. Place 4 tiles vertically in the first four rows and 1 tile horizontally in the last row.

3. Place 1 tile horizontally in the first row and adjust 4 tiles vertically in the remaining rows.

Similarly, there are 4 ways to place `1 x 4` tiles in a `6 x 4` matrix –

1. Place all 6 tiles horizontally.

2. Place 4 tiles vertically in the first four rows and remaining 2 tiles horizontally in the last two rows.

3. Place 2 tiles horizontally in the first two rows and adjust the remaining 4 tiles vertically in the remaining rows.

4. Place 2 tiles horizontally in the first & the last row and adjust the remaining 4 tiles vertically in the middle rows.

From the above examples, it is evident that a single tile can be placed horizontally or 4 tiles can be placed together vertically (since the matrix has dimensions `n x 4`). So the problem of computing the number of ways `T(n)` for a `n x 4` matrix can be broken down into the subproblems of computing `T(n-1)` and `T(n-4)`, and then adding the two. Considering this, the recurrence relation `T(n)` can be written as:

T(n) = T(n-1) + T(n-4) where n > 4 and
T(1) = T(2) = T(3) = 1   // all tiles can be placed only horizontally for n <= 3
T(4) = 2                 // all tiles can be placed either horizontally or vertically.

Here's a C program that implements the above recurrence:

Output:

Total number of ways are 3

The time complexity of above solution is exponential since it computes solutions to the same sub-problems again and again i.e. the problem exhibits overlapping subproblems.

We can easily solve this problem using Dynamic Programming. The idea is to construct a temporary array which stores the results of each sub-problem using already computed results of the smaller sub-problems. The algorithm can be implemented as follows in C:

Output:

Total number of ways are 3

The time complexity of above solution is `O(n)` and auxiliary space used by it `O(n)`. The program can be made to run in constant space by storing solutions to only last four sub-problems at any point and discarding the rest. The space efficient implementation is left as an exercise to the readers.     (2 votes, average: 5.00 out of 5) Loading... 