Tri Tiling - Dynamic Programming

In the previous article, we have completed the theoretical perspective of Dynamic Programming and we reached a stage when we have to practice problems and learn different concepts (or) frameworks of solving problems. Let's start.

Image Source: Google

Thing's to be discussed here.

Tri Tiling Problem
Practice Problems

Tri Tiling ( POJ )

Problem Statement: Given n, find the number of ways to fill a 3 * n board with dominoes of 2 * 1 size.

Solution: The given question asks us to find the number of ways to fill a 3 * n board with dominoes of size 2*1.

Now to solve this problem we need to find the recurrence relation.

Step 1: Define Subproblems

Let D_n be the number of ways to fill a board of size n and Gn be the number of ways to fill a board with one corner removed.

Step 2: Find a recurrence relation that relates to the subproblems.

Now from the above figure A, imagine that we have a board of size 3 * n with 3 rows and n columns which we can denote by 1, 2, 3, ... , n-1, n. Now let us say that we fill last (nth) cell by 2 * 1 dominoes horizontally as shown in figure A then the remaining board size would be n-2.

Then we can get the number of ways to fill 3 * (n-2) board by D_n-2.

Another case will be in the form of figures B and C that is we fill with one horizontal and one vertical dominoes. Now if the arrangement is like figure B i.e bottom corner is already filled. Then the number of ways to fill the remaining 3*(n-1) board is equal to G_{n-1_.}
Similarly, for figure C the number of ways to fill the 3*(n-1) board is equal to G_n-1.
So the total number of ways we got is D_n = D_n-2 + 2*G_n-1

Now let us define of G_n,

Now from figure D, we observe that one way to fill a board of size 3*n with one corner removed is that we fill the nth column with 2*1 tile vertically then the remaining 3*n-1 board can be filled in D_n-1 way.
Another way to fill the last col is to fill in the way we have filled-in figure E to and fill the remaining 3*n-1 board with G_n-2 ways.
So the total ways of filling 3*n board with one corner removed are G_n = D_n-1 + G_n-2.
With this, we define the value of G_n.

Therefore recurrence relation is,

D_n = D_n-2 + 2*G_n-1
G_n = D_n-1 + G_n-2.

Step 3: Recognise and solve for the base cases.

Let us take n as odd then is it possible to fill the board with 2*1 dominoes without breaking, no. The simple answer is that number of blocks would be odd so we can't fill it.
Now with proper observation, we can get that D₀ = 0, D₁ = 1, G₀ = 0, and G₁ = 1. And hence done.

Huhahhh.... we have solved the problem, now you can code this simple problem and submit it to POJ.

Practice Problems

Summary:
Today we solved a 1-dimensional DP problem. Using these steps

Define Subproblems
Write down a recurrence that relates the subproblems
Recognize and solve the base cases. ( This is also called as initial states (one or more) )

Then we have solved one problem from scratch using the above 3 steps. We have provided you with some Practice Problems do try them out.

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You & Regards

Tri Tiling - Dynamic Programming

Post a Comment

Contact Form