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.

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

We will solve some other

If you have some

Thank You

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

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

**problems**in the next article, and learn some different concepts with the hope that you have fully understood all the previous concepts.

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

## Comments

## Post a Comment