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.

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂