# DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

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?

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