[Solved]: Tile Problem : Dynamic Programming

Problem Detail: 

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?

Asked By : Aman Gupta

Answered By : sashas

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54780

 Ask a Question

 Download Related Notes/Documents