a bit of dp: SPOJ - M3TILE

Problem Statement:
SPOJ - M3TILE

Summary:
Compute the number of ways to place 1x2 tiles onto 3xN board. ( \( N \leq 30 \) )

Solution:
Years ago when I was in junior high school, I was presented with a similar combinatorics problem during a mathematics competition. The dimension was small, around 3x9 or 3x10. I was not familiar with the idea of recursion that time, so I tried to generate the tilings and desperately trying to find a pattern (haha). Anyway, the key to this problem is finding a suitable recursive relationship and use DP to cache the answers to each N, pretty simple.

Firstly let's agree that the number of ways to tile 3x0 board is 1 (in which we don't place any tiles at all). Now let S(n, k) be the number of ways to place the tiles on a 3xN boards with grid [1..k] on the N-th column covered. Then our job is just to consider each case one by one and figure out what is the recursive relation S of lower valued n. We have
\(S(n, 0) = 2S(n-1, 1) + S(n-2, 0) \)
\(S(n, 1) = S(n-1, 0) + S(n-1,2) \)
\(S(n, 2) = S(n-1, 1) \)
The answer will be S(N,0) for each N.