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?