Dynamic Programming ( DP - 3 )

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 Dn 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 Dn-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 Gn-1.
  • Similarly, for figure C the number of ways to fill the 3*(n-1) board is equal to Gn-1.
  • So the total number of ways we got is Dn = Dn-2 + 2*Gn-1
Now let us define of Gn,

  • 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 Dn-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 Gn-2 ways.
  • So the total ways of filling 3*n board with one corner removed are Gn = Dn-1 + Gn-2.
  • With this, we define the value of Gn.
Therefore recurrence relation is,
  • Dn = Dn-2 + 2*Gn-1
  • Gn = Dn-1 + Gn-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 D0 = 0, D1 = 1, G0 = 0, and G1 = 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.

We will solve some other 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