Problem Link - Number of Tilings
Problem Statement
You have to tile a room that is two units wide and N units long. You have with you two types of tiles: a rectangle that is one unit wide and two units long, and an L - shaped tile covering three square units. You are allowed to rotate the tiles when you lay them. You have an infinite supply of both types of tiles. Your objective is to calculate the number of different ways of tiling the room using these tiles.
For instance, a 2×3 room can be tiled in 5 different ways, as follows:
Notice that a tiling can use both types of tiles. Consider, for instance, the following tiling of a 2×4 room.
Given N, your task is to determine the number of ways to tile a room of size 2×N. Since this number may be very large, it is sufficient to report the last four digits of the answer. For instance, the number of ways to tile a 2×13 room is 13465. Your program should just print 3465. If the answer involves fewer than 4 digits then print the entire answer. For example, if N = 3 you should print 5.
Approach
To solve this problem, we can think of it in terms of dynamic programming. We will maintain a list that stores the number of ways to tile a 2×i room for all i from 1 to N. For the base cases, we know the following: there is 1 way to tile a 2×1 room (by placing a vertical tile), 2 ways to tile a 2×2 room (two vertical tiles or two horizontal tiles), and 5 ways to tile a 2×3 room (combining both types of tiles in different ways). Once we have these base cases, we can use the following recurrence relation to compute the number of ways to tile a 2×N room:
- The number of ways to tile a 2×i room is a combination of the ways to tile a 2×(i-1), 2×(i-2), and 2×(i-3) room. This is because we can add either a 2×1 vertical tile, a 2×2 square arrangement of tiles, or a 2×3 L - shaped tile, and recursively tile the remaining space. At each step, we update the number of ways to tile the room, and we ensure the result is modulo 10000, as we only need the last four digits.
Time Complexity
The time complexity of the solution is O(N), as we are computing the number of ways for each length up to N in a linear fashion.
Space Complexity
The space complexity is O(1), since we only need a fixed amount of space to store the current and previous values during the computation.