Tiling With Dominos(DP solution)

Правка en1, от slow.coder, 2015-09-24 21:07:43

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

Теги dynamic programming, tiling blocks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский slow.coder 2015-09-25 00:41:29 1
en2 Английский slow.coder 2015-09-24 21:11:02 8 Tiny change: 'vanced. :)' - (published)
en1 Английский slow.coder 2015-09-24 21:07:43 1079 Initial revision (saved to drafts)