2
$\begingroup$

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php

The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile.

Question 1) In the recursive formula for g(n):

g(n) = f(n-1) + h(n-1)

Why didn't we include the case that we can also put a 2x1 tile horizontally on the top row. Something like -

g(n) = f(n-1) + h(n-1) + x(n-3)

where f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2) still holds.

Basically, are we not looking into the cases how we can start tiling from the state g(n) ? ither we add an L-shaped tile, and look at f(n-1), or we add a 2x1 tile in the bottom layer and look at h(n-1), or add a 2x1 tile in the top layer and look at x(n-3) ?

Question 2) It seems like while writing the recursion, we should only deal with cases that we have already named, i.e. only moving from state g(n) to h(n-1) or moving from state g(n) to f(n-1) ? Is it true, that when once we have decided which states to deal with, we only consider those states?

$\endgroup$
  • $\begingroup$ Why don't you try proving that the stated recurrence works? The proof should assuage all your fears. $\endgroup$ – Yuval Filmus Dec 17 '17 at 8:39
  • $\begingroup$ FYI: The same tiling problem has been considered here: "Domino and Tromino Combined Tiling". This of course does not directly answer your questions. $\endgroup$ – Hendrik Jan Dec 17 '17 at 15:05
1
$\begingroup$

Q1. Of course you can consider a third variable in the recursion, but that would not simplify the analysis. In fact from the case where you put the single horizontal domino, the next step would automatically put the second horizontal one below it. So the given recursion takes a little shortcut.

Q2. That is precisely the point. We have to make sure the analysis steps from existing state to existing state, in a kind of unique way. If we overlook a state we miss possibilities. But here we easily see how the states are related, and how we step from one to another.

$\endgroup$

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.