Table of contents

Introduction

1.1.

Problem Statement:

1.2.

Example

Recursion

2.1.

Implementation

2.1.1.

Program

2.1.2.

Input:

2.1.3.

Output:

2.2.

Time Complexity

2.3.

Space Complexity

Dynamic Programming

3.1.

Implementation- Top-Down Approach

3.1.1.

Algorithm

3.1.2.

Program

3.1.3.

Input:

3.1.4.

Output:

3.2.

Implementation- Bottom-Up Approach

3.2.1.

Algorithm

3.2.2.

Program

3.2.3.

Input:

3.2.4.

Output:

3.3.

Time Complexity

3.4.

Space Complexity

Key Takeaways

Last Updated: Mar 27, 2024

Tiling Problem

Author Ishita Chawla

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Some questions can be solved very simply by identifying a pattern being followed and using the concept of Fibonacci numbers.

Fibonacci numbers follow the following sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…..

The recurrence relation for the sequence is given by

The Fibonacci pattern can be observed in nature, and it is often considered a fundamental problem of dynamic programming.

This is because instead of calculating the results, again and again, we store the results of the subproblem, which helps prevent recalculations.

For example, let N = 5.

The recursion tree for this would be:

Let us look at one such problem that is equally important from an interview perspective and primarily based on identifying the pattern.

Problem Statement:

Consider a board of size 2 * N and tiles of size “2 * 1”. You have to count the number of ways in which tiling of this board is possible. You may place the tile vertically or horizontally, as per your choice.

Let us understand the problem with the help of a few examples:

Example

N = 4

The tiling of this board is possible in 3 different ways. Let us see how:

All 4 bricks can be placed vertically.

All 4 bricks can be placed horizontally.

2 bricks can be placed horizontally and 2 vertically.

2. N = 3

The tiling of this board is possible in 2 different ways. Let us see how:

All 3 bricks can be placed vertically.

2 bricks can be placed horizontally and 1 brick vertically.

3. N = 5

The tiling of this board is possible in 3 different ways. Let us see how:

All 5 bricks can be placed vertically.

4 bricks can be placed horizontally and 1 vertically in 2 different ways.

2 bricks can be placed horizontally and 3 vertically in 2 different ways.

Now, let us solve this Tiling problem using recursion, and then we will see how and why it can be optimized using Dynamic Programming:

Recursion

We will solve this problem using recursion. We will start to tile the board from the last column, i.e.; we will first tile the N^th column, then (N-1)^th column, and so on.

There are 2 cases possible:

If we place the tile vertically, the problem will be converted into a sub-problem of tiling a board of size 2 * (N - 1).
If we place the tile horizontally, 2 tiles will be required to cover the N^th and (N - 1)^th column, and now the problem will be converted into a sub-problem of tiling a board of size 2 * (N - 2).

Thus, if countOfWays(N) denotes the number of ways to tile a board of size 2 * N, then,

If you observe, this pattern follows the Fibonacci Sequence. Hence its implementation is also the same.

Implementation

Program

/* C++ program to count the number of ways to place 2 * 1 size tiles on a 2 * n size board using recursion.*/

#include <iostream>
using namespace std;

// Function to calculate the total number of possible ways of tiling a board.
int numOfWays(int n)
{
    // Base case.
    if (n == 0 || n == 1)
        return n;

    return numOfWays(n - 1) + numOfWays(n - 2);
}

int main()
{
    int n;
    // Taking user input.
    cout << "Enter the value of N: ";
    cin >> n;

    // Calling the function to predict the output.
    cout << "The total number of possible ways to place the tiles on the board are " << numOfWays(n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Enter the value of N: 5

Output:

The total number of possible ways to place the tiles on the board is 5.

Time Complexity

The time complexity of this technique is exponential and is given by O(2^N), where 2 * N is the size of the board.

The function uses Recursion, and in the worst case, it makes 2 calls for every N. Thus, the time complexity is O(2^N).

Space Complexity

The space complexity is O(N), where ‘N’ is the length of the board.

In any case, there will be a maximum of ‘N’ function calls that will occupy O(N) space of the recursion call stack. Hence, the space complexity is given by O(N).

Now, we will see why and how the solution can be optimized using DP.

Dynamic Programming

The logic to solve this problem remains the same. But if we take a closer look at the above explanation, we see several repetitive calculations. Thus, the problem can be considered to have a number of sub-problems, and we can store the result of these sub-problems in an array and use these results.

This method significantly reduces the time complexity of the problem.

Implementation- Top-Down Approach

This approach uses recursion + memoization and breaks the problem into smaller sub-problems. The computation of subproblems is avoided if the sub-problem has already been solved before or their results are stored.

Algorithm

The output of the recursive calls can be stored in a memoization array. Before calling the recursive function, we initialize the DP array with a value equal to -1.
Before the recursive call is made, we first check whether the output is already present in the memoization array or not.
If it has already been calculated, we return the result. This helps in avoiding repetitive calculations as the value is calculated for every subtree only once.
If it’s not calculated, the result is stored in the memoization array.

Program

/* C++ program to count the number of ways to place 2 * 1 size tiles on a 2 * n size board using top-down approach of Dynamic Programming.*/

#include <iostream>
#include <cstring>
using namespace std;

int dp[1000];

// Function to calculate the total number of possible ways of tiling a board.
int numOfWays(int n)
{
    // Base case.
    if (n == 0 || n == 1)
        return n;

    // If the value has been computed before, it will be returned.
    if (dp[n] != -1)
        return dp[n];

    return dp[n] = numOfWays(n - 1) + numOfWays(n - 2);
}

int main()
{
    int n;
    // Taking user input.
    cout << "Enter the value of N: ";
    cin >> n;

    // Initialising the dp array with -1.
    memset(dp, -1, sizeof(dp));

    // Calling the function to predict the output.
    cout << "The total number of possible ways to place the tiles on the board are " << numOfWays(n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Enter the value of N: 5

Output:

The total number of possible ways to place the tiles on the board is 5.

Implementation- Bottom-Up Approach

It involves the calculation of smaller sub-problems to compute the result of larger sub-problems. We store the results of the smaller sub-problems in a DP array and use these to calculate the result of the larger sub-problem. Let’s see how we can solve the Tiling Problem using this approach.

Algorithm

We declare a DP array of size N before calling the recursive function to store the results of the calculations.
We find a base case for the recursion and then store the result at every step in this DP array.
If the result is already present in the array, we need not calculate it again,
Else we use the DP array to calculate our answer.

Program

/* C++ program to count the number of ways to place 2*1 size tiles on a 2 * n size board using the bottom-up approach.*/
#include <iostream>
using namespace std;

// Function to calculate the total number of possible ways of tiling a board.
int numOfWays(int n)
{
    // Memoization array to store the total possibilities.
    int dp[n + 2];
    int i;

    // The first 2 numbers of the sequence are 0 and 1.
    dp[0] = 0;
    dp[1] = 1;

    // To calculate the result using the previous 2 results and to store it in the array.
    for (i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // Returning the nth number.
    return dp[n];
}
int main()
{
    int n;
    // Taking user input.
    cout << "Enter the value of N: ";
    cin >> n;

    // Calling the function to predict the output.
    cout << "The total number of possible ways to place the tiles on the board are " << numOfWays(n);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Enter the value of N: 5

Output:

The total number of possible ways to place the tiles on the board is 5.

The time and space complexity for DP remains the same no matter what the approach is bottom-up or top-down. Let’s take a look at these.

Time Complexity

The time complexity is given by O(N), where 2*N is the size of the board that needs to be tiled.

Since we are using DP to store the results, every combination is computed only once. Hence, the time complexity of this approach is given by O(N).

Space Complexity

The space complexity is given by O(N), where 2*N is the size of the board that needs to be tiled.

Since we are using extra space to store the results and avoid recalculation, the space complexity is given by O(N).

Also check out - Rod Cutting Problem

Key Takeaways

So, this blog discussed one of the most fundamental topics of Dynamic Programming and discussed how Fibonacci patterns play an essential role in solving problems.