slow.coder's blog

By slow.coder, history, 8 years ago, In English

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

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?