題目連結：
題目大意：
已知導盲磚為寬度為 ２ 單位，長度為 ｎ 單位長的矩形。現有 ２ × １ 、 １ × １ 兩種磁磚。給定一正整數 Ｋ ，代表接下來有 Ｋ 列輸入。每列輸入有一正整數 ｎ （ ｎ ≦ ３０ ），求有多少種排列方式。
下圖分別為 ｎ ＝ １ 、 ｎ ＝ ２ 、 ｎ ＝ ３ 的情況：
範例輸入：
3
1
2
3
範例輸出：
2
7
22
解題思維：
題目的圖示有做一些提示。
我們可以看到藍色虛線區域的方法數是由 ｎ － ２ 的方法加上 ２ 個 ２ × １ 矩形所形成。
還有那些沒有被框起來的方法是由 ｎ － １ 的方法分別加上「１ 個 ２ × １」或是 「２ 個 １ × １ 」所成。
但是紅色虛線的區域則比較特別。以下稱 ｎ 的方法數為 Ｆｎ ，而面積為 ２ × ｎ 但是最右上或最右下缺一個 １ × １ 的磚道方法數為Ｇｎ 。
所以我們可以觀察到紅色區域即為 Ｇｎ－１ 。而 Ｇｎ 的值是由 ２ × Ｆｎ－１ ＋ Ｇｎ－１ 過來的。因為可以在 Ｆｎ－１ 最右上或最右下放 １ 個 １ × １ 的磁磚、在 Ｇｎ－１ 的缺口放 １ 條 ２ × １ 的矩形。
而現在我們知道 Ｆｎ 為 ２ × Ｆｎ－１ ＋ Ｆｎ－２ ＋ Ｇｎ－１ 。因此Ｇｎ可以簡化為
Ｇｎ ＝ Ｆｎ － Ｆｎ－２
而把上式帶回 Ｆｎ 的式子可以得到
２ × Ｆｎ－１ ＋ Ｆｎ－２ ＋ （Ｆｎ－１ － Ｆｎ－３）
因此，ｎ 的方法數 ＝ Ｆｎ ＝ ３ × Ｆｎ－１ ＋ Ｆｎ－２ － Ｆｎ－３。
接著，就照著上面的遞迴式將 ｎ ≦ ３０ 的方法數全部預先算出，看輸入什麼數字，再輸出相應的答案。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
