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. :)
