Came across the following tile problem :
Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
Recurrence formula is as mentioned below :
count(n) = n if n = 1 or n = 2
count(n) = count(n-1) + count(n-2)
Explanation is as follows :
count(n-1) : If the first tile is placed vertically, then problem reduces to a grid of size "2 x (n-1)"
count(n-2) : If the first tile is placed horizontally, then problem reduces to a grid of size "2 x (n-2)", because we will need to place two tiles horizontally one above the other
But my doubt is, the above recurrence is fine if we always place the tiles at the left most side of grid. What if I place the first vertical tile at center of grid instead of the left most. Should not be covering all the permutation and combinations possible on basis of where we place the first tile?
