2
$\begingroup$

http://www.algorithmist.com/index.php/UVa_10918

The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely different. I want to understand the given approach. The problem is:

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

I only want to know how these recurrence relations came:

f(n)=f(n-2)+2*g(n-1)
g(n)=f(n-1)+g(n-2)

where f(n)=number of tilings of a 3xN rectangle g(n)= number of tilings of a 3xN rectangle with one of its corner squares removed

$\endgroup$
  • 1
    $\begingroup$ It is explained on the site. So can you be more explicit as to what you do not understand? $\endgroup$ – babou May 5 '15 at 14:12
  • 1
    $\begingroup$ What have you tried and where did you get stuck? Hint: correctness of recurrences is typically shown by induction (here on $n$). $\endgroup$ – Raphael May 5 '15 at 15:19
6
$\begingroup$

Suppose that the rectangle to be tiled has 3 rows and $n$ columns.

□□□...□
□□□...□
□□□...□
123...n

Consider a tiling of this rectangle using 2$\times$1 dominos. There are two basic options:

  1. All tiles touching the $n$th column are horizontal. There must be 3 of them, and if you remove them, you get a tiling of a rectangle of size $3\times(n-2)$.

    □□□...⧆⧆
    □□□...■■
    □□□...⧆⧆
    123....n
    
  2. Exactly one tile touching the $n$th column is vertical. It can either touch the top or the bottom. For each of these two options, if you remove it then you get a tiling of a rectangle of size $3\times (n-1)$ with one corner square added. That square must be tiled by a horizontal tile, after whose removal you are left with a tiling of a $3\times(n-1)$ rectangle with one corner square removed added.

    □□□...⧇⧇      □□□...□⧆
    □□□...□⧆      □□□...□⧆
    □□□...□⧆      □□□...⧈⧈
    123....n      123.....n
    
        |             |
        V             V
    
    □□□...□□     □□□...□
    □□□...□      □□□...□
    □□□...□      □□□...□□
    123....n     123....n
    

This explains the formula $f(n) = f(n-2) + 2g(n-1)$.

The same sort of analysis yields the formula for $g(n)$, but I leave that one for you.

$\endgroup$
8
$\begingroup$

The picture should say more than words.

2x1 domino's on a 3xn strip

$\endgroup$
  • 1
    $\begingroup$ But if you need the words, see the answer by @Yuval-Filmus. $\endgroup$ – Hendrik Jan May 5 '15 at 13:51
  • 1
    $\begingroup$ Sorry. As @babou observes above the first link in the question has some explanation and these pictures (albeit as ascii art). So how can they help? $\endgroup$ – Hendrik Jan May 6 '15 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.