Tiling Problem Using Dynamic Programming in C++

Today we will learn to solve the tiling problem using dynamic programming. First, we will briefly discuss the problem statement and then we will move to the implementation. This problem is a popular interview problem related to recursion. So without wasting any time, let’s get started.

Problem Statement

Given a wall of size (4 x N), and tiles of size (1 x 4) and (4 x 1). Find the total number of ways to tile the wall using the given tiles.

Approach to Solving the Tiling Problem using Dynamic Programming

To solve this problem we will build the algorithm in the following order.

One can either place the brick vertically or horizontally
If you place the first tile vertically, then you are left with a wall of size (4 x (N – 1)).
- To find the solution to this problem, make a recursive call to the same function but with N = (N – 1).
Otherwise, if you place the first tile horizontally
- Then you are left with a wall of size (4 x (N – 4)).
- This is because, to tile the remaining 3 rows out of 4 rows, you have no choice other than tiling them horizontally as well.
Apart from these two cases, there are no other cases.
Hence the solution for a wall of size N boils down to the following expression.
- f(N) = f(N – 1) + f(N – 4).
Base Cases
- If the value of N less than 4, then there is only one arrangement possible
- If the value of N is 4 then we can have 2 different arrangements.

Pseudocode

tile_the_wall(N)

{

if (N < 3)

return 1

if (N == 4)

return 2

return tile_the_wall(N - 1) + tile_the_wall(N - 4)

}

But the above approach is a naive implementation. We can optimize the solution using a dynamic programming approach. It is clearly noticeable that we are making repetitive calls to the same subproblem for different values of N. This ends up calculating the solution to the same subproblem again and again. Ultimately leading to very poor time complexity and a huge recursion tree.

In the dynamic programming approach, we simply store the solution to these repetitive subproblems using a vector. And whenever we need these values, we have their access in constant time complexity. Let’s quickly go through the pseudocode of this optimized algorithm.

tile_the_wall_optimized(N)

{

if (N < 3)

return 1

if (N == 4)

return 2

if(dp[N] != 0)

return dp[N]

return dp[N] = tile_the_wall_optimized(N - 1) + tile_the_wall_optimized(N - 4)

}

#include <iostream>

#include <vector>

using namespace std;

// vector to store the solution to intermediate states

vector <int> dp(10000, 0);

// naive implementation

int tile_the_wall(int N)

{

// base cases

if(N < 4)

return 1;

if(N == 4)

return 2;

// the recursive relation is:

// f(N) = f(N - 1) + f(N - 4)

return tile_the_wall(N - 1) + tile_the_wall(N - 4);

}

// dynamic programming approach

int tile_the_wall_optimized(int N)

{

// base cases

if(N < 4)

return 1;

if(N == 4)

return 2;

// lookup step

if(dp[N] != 0)

return dp[N];

// the recursive relation is:

// f(N) = f(N - 1) + f(N - 4)

return dp[N] = tile_the_wall_optimized(N - 1) + tile_the_wall_optimized(N - 4);

}

int main()

{

cout << "Enter the value of N" << endl;

int n;

cin >> n;

cout << "Naive Approach Solution: " << tile_the_wall(n) << endl;

cout << "Optmized Approach Solution: " << tile_the_wall_optimized(n) << endl;

}

Output:

Enter the value of N

5

Naive Approach Solution: 3

Optmized Approach Solution: 3

Time And Space Complexity Analysis

The time complexity of the naive approach becomes exponential in nature. More precisely it is of the order O(2N). And the space complexity of this approach is constant except for the space needed for the recursion stack.

For the dynamic programming approach, the time complexity becomes linear, i.e. O(N). And the space complexity is also linear along with the space required for the recursion stack.

Conclusion

In this article, we learned naive and dynamic programming solutions to the tiling problem. Initially, we discussed the problem statement, later we looked at both the approaches (brute force and DP). In the end, we wrote a C++ program to demonstrate both algorithms. That’s all for today, thanks for reading.

Tiling Problem Using Dynamic Programming in C++

Problem Statement

Approach to Solving the Tiling Problem using Dynamic Programming

Pseudocode