In short, You are given the value of **N**, now determine in how many ways you can completely tiled a **3xN** rectangle with **2x1** dominoes. Here is a possible soln: Algorithmist — UVa 10918. My question is, how is the recurrence defined? Here,

```
******** AA******* AA****** A*******
******** = BB******* + B******* + A*******
******** CC******* B******* BB******
f(n) = f(n-2) + g(n-1) + g(n-1)
```

Isn't it possible as:

```
******** AA******* AA****** AA******
******** = BB******* + BA****** + AA******
******** CC******* BA****** BB******
f(n) = f(n-2) + f(n-2) + f(n-2)
```

or like others....(actually I want to know it). How can I define such type of recurrence?

*Actually I want to know, what type of thinking should I keep in mind while defining recurrence for Tiling Block problem???*

Thanks in advanced. :)

Auto comment: topic has been updated by slow.coder (previous revision, new revision, compare).You don't have to do it in O(N) time...

You can continue to put dominoes and do it in O(N^2)... (I wish I'm not wrong)

For example:

NOTE : I want to sleep now and don't have time but I think maybe you can do this in O(N) too...by saving sum of all f(2i) and f(2i+1) in two integers

@Sa1378

Ok. But why

is the recurrence??? Suppose, I know nothing about the given recurrence in the soln, then how can I feel the idea of recurrence??? Let it is

4xN(, 5xN, 6xN,....., MxN)then what would be the recurrence relation? How can I develop it step by step?http://mewtomat.blogspot.com/2016/03/spoj-gny07h-tiling-grid-with-dominoes.html

Searching for good tutorials about dynamic programming approach for this problem, I have accidentally found this presentation. The guys claim they can find the number of domino tilings of the

m×nrectangle in polynomial time (it seems likeO((nm)^{3}) algorithm). I haven't had time to understand the full presentation yet, but this fact was quite unexpected to me. Have you guys heard about it before? :)Yes, for example, see acm.timus.ru problem "Aztec treasure" ("Сокровища ацтеков"), here is such problem for 100x100 grid =))

This interesting method firstly was presented to ACM in Petrozavodsk winter camp 2009. Team of Yekaterinburg try to tell us solution, which was described in some big article (40-50 pages in size).

If you want, I can see for some hint or link for you.

Can you give me this article, please? I solved this problem several years ago but almost forgot solution.

Proof: http://acm.timus.ru/status.aspx?space=&num=1594&author=64460

Ok, I can search it in the evening later... Don't promise that really have this article now, I'm not sure.

time is O((n+m)^3), not O((n*m)^3)

As for your question, you can find some clues in this tutorial.

@Kostroma

Truth to tell I have already found the tutorials which you have referred.... Please give your idea if any to understand the psychology of the recurrence of

Tiling Blockproblem soln.... :)Thanks for your link, It's very helpful and fun also =))

I found this useful when I was first learning how to solve these types of problems.

@Governer

WoW!!! This is an awesome tutorial. Thanks!!!

But, In the first answer I have some confusions:(picture is taken for clearance)>>> Here F extended by itself!!! Ok, fine!!!Now it says,

>>> How G could be extended by A (If so then, why not E?), D (Isn't it C?) and H (Isn't it G itself)?>>> How H could be extended by A (If so then, why not E?), C (Isn't it D?) and G (Isn't it H itself)?Ok !!! after changing the following things the main result would be same. But the main confusion is here,

".....could be extended by A (If so then, why not E?)"