CODEWITHSUNDEEP
algorithmdynamic-programmingcombinatorics
Jignesh
Jignesh

Reputation: 565

Solving Tiling Problems

I recently came across this problem in a contest:

How many ways are there to fill a 4*N board completely using only tiles of 1*4 and 4*1 dimensions?

Working through many cases, we figured out that 

  f(i) = f(i-1) + f(i-4) ; (i > 4)

is the solution to this problem (Dynamic Programming). But still we werent sure of this answer before we submitted and got AC.

So can anyone explain me how does one arrive at the above formula, as it is not intuitive to me. Also what if the problem statement was changed and we had to use tiles of dimensions 2*3 and 3*2, then what is the recursive formula? So in essence I want to know how to solve such tiling problems, what is the approach. Any good reference links are welcome.

Thanks

Upvotes: 0

Views: 1661

Answers (2)

Scott Hunter
Scott Hunter

Reputation: 49803

Assume the grid is N across & 4 high. You have 2 choices for how to cover the top-left spot: you can cover the leftmost column with a single tile, which is your f(i-1) term; or you can cover the top row of the first 4 columns, forcing you to cover the rest of those columns with similarly-oriented tiles, giving the f(i-4) term.

Upvotes: 3

Garrett Openshaw
Garrett Openshaw

Reputation: 304

"So in essence I want to know how to solve such problems, what is the approach. Any good reference links are welcome."

MIT Opencourseware has an intro to algorithms class. Here is a link to that class' lecture for Dynamic Programming.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-15-dynamic-programming-longest-common-subsequence/

Good luck!

Upvotes: 0

Related Questions