Why does it happen? (Post — 2)

Revision en2, by slow.coder, 2015-10-06 15:23:47

SPOJ Problem: Tiling a Grid With Dominoes

In short: You are given the value of N, now determine in how many ways you can completely tiled a 4xN rectangle with 2x1 dominoes.

We can solve this problem using DP technique, when the recurrence relation is:

f[n] = f[n - 1] + 5 * f[n - 2] + f[n - 3] - f[n - 4];

Here is a great explanation: count the ways to fill a 4×n board with dominoes. Thanks to draughtsman for providing such a wonderful tutorial link. :)

Tags tiling blocks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English slow.coder 2015-10-06 15:23:47 90
en1 English slow.coder 2015-10-06 09:11:38 586 Initial revision (published)