Tile Problem : Dynamic Programming

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?

Your understanding of reducing the given problem to a subproblem is flawed. Say you have to place the tiles, if you start from the centre and keep on placing the tiles, finally the arrangement you have can also be obtained by placing tiles from the left hand side. You don't want to double count. So the recurrence relation you mentioned is correct.

StackExchange Computer Science Q#54780, answer score: 4