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