Tiling With Dominoes(DP solution)

Revision en3, by slow.coder, 2015-09-25 00:41:29

UVa 10918 — Tri Tiling.

In short, You are given the value of N, now determine in how many ways you can completely tiled a 3xN rectangle with 2x1 dominoes. Here is a possible soln: Algorithmist — UVa 10918. My question is, how is the recurrence defined? Here,

********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

Isn't it possible as:

********   AA*******   AA******   AA******
******** = BB******* + BA****** + AA******
********   CC*******   BA******   BB******
  f(n)   =  f(n-2)   +  f(n-2)  +  f(n-2)

or like others....(actually I want to know it). How can I define such type of recurrence?

Actually I want to know, what type of thinking should I keep in mind while defining recurrence for Tiling Block problem???

Thanks in advanced. :)

Tags dynamic programming, tiling blocks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English slow.coder 2015-09-25 00:41:29 1
en2 English slow.coder 2015-09-24 21:11:02 8 Tiny change: 'vanced. :)' - (published)
en1 English slow.coder 2015-09-24 21:07:43 1079 Initial revision (saved to drafts)