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.

**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}

- Then we can get the number of ways to fill 3 * (n-2) board by
- 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**ways._{n-2} - 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}= 0, D_{1}= 1, G_{0}= 0, and G_{1}= 1. And hence done.

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

**Practice Problems**

- Prime Permutations ( CodeChef )
- Enormous Input Test ( CodeChef )
- T-Primes ( 230B )
- Frog 1 ( AtCoder )
- Frog 2 ( AtCoder )
- Before an Exam ( 4B )
- Cheap Travels ( 466A )
- Flowers ( 474D )
- Given the length and sum of digits ( 489C )
- Woodcutters ( 545C )
- Number of ways ( 466C )
- Two Substrings ( 550A )
- Quasibinary ( 538B )
- Doraemon and WiFi ( 476B )
- Fence ( 363 B )

**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. With this, we complete the theory perspective of Dynamic Programming and here we provide you with some problem to Practice.

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