首先，題目說要用面積為2的磚塊填滿3 x n的區域，所以n只允許偶數，奇數的方法數量為0。
接下來，先看看n=2的情況，有3種排法，稱作基礎排法:
11   11   23
22   23   23
33   23   11
設函數f(n)為3 x n的所有排法數，我們已經知道f(2) = 3。n=0的方法數只有一種，所以f(0) = 1。

再來看看n=4的情況，簡單推算可以知道n=4其實可以看成n=2再加上一組基礎3 x 2區域，而這又有3種方法，所以f(4) = 3 x f(2)。但是有兩個排法也是3 x 4但沒辦法用組合的方式得到，這兩個特殊排法是鏡向的:

1122   3664

3554   3554

3664   1122

而這兩種排法也可以看成是由n=0再加上兩種3 x 4特殊排法，所以最後f(4) = 3 x f(2) + 2 x f(0)。

繼續往下，n=6，這是由n=4再加上一組基礎3 x 2區域，也是n=2再加上3 x 4特殊排法，也是n=0再加上3 x 6特殊排法，3 x 6特殊排法如下:
112233   488995

466775   466775

488995   112233

所以f(6) = 3 x f(4) + 2 x f(2) + 2 x f(0)。

不難發現，對於任何大於2的偶數的n，3 x n都只有兩種特殊排法，例如3 x 4和3 x 6和3 x 8甚至3 x 100，他們都只有兩種特殊排法，所以f(n)為f(n-2)再加上基礎3 x 2區域、f(n-4)加上3 x 4特殊排法、f(n-6)加上3 x 6特殊排法、f(n-8)加上3 x 8特殊排法......

最終可以得到一個關係式:
f(n) = 3*f(n-2) + 2*f(n-4) + 2*f(n-6) + 2*f(n-8) + ... + 2*f(0)

接下來要精簡這個公式
考慮f(n-2) = 3*f(n-4) + 2*f(n-6) + 2*f(n-8) + ... + 2*f(0)

將f(n)減去f(n-2)得到f(n) - f(n-2) = 3*f(n-2) - f(n-4)

移項整理得f(n) = 4*f(n-2) - f(n-4)，這個就是本題關鍵的遞迴關係式。
所以可以在剛開始建一個大小為31一維陣列，設定初始值f[0] = 1、f[2] = 3，f[i] = 4 * f[i-2] - f[i-4]，這樣所有的方法數都計算出來了。

附上我的C++程式碼: