題目描述：
Problem Description
In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.
Input
Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.
Output
For each test case, output one integer number giving the number of possible tilings.
Sample Input
2
8
12
-1
Sample Output
3
153
2131
題目分類：遞推，DP
因為我對DP不熟，所以我用數(shù)學(xué)遞推抹恳，由于我不是能一眼就看出規(guī)律，所以只能用最笨的方法——畫。
這道題的意思是：有一個3n的矩形肢藐，先給你12的小矩形（個數(shù)不限）别渔，問你要用小矩形把大矩形填滿，有多少種方案匾灶。
個人方法：
這道題如果畫出前面幾個你就會發(fā)現(xiàn)棱烂，如果n是奇數(shù)的話是不可能填滿大矩形的，所以方案為0阶女；當(dāng)n為偶數(shù)時根據(jù)畫圖的方案數(shù)可以推出規(guī)律颊糜。
綜上所述：遞推公式為f(n) = 4 * f(n-2) - f(n-4).
特別的：f(0) = 1,f(1) = 0,f(2) = 3,f(3) = 0.
參考代碼：
#include <iostream>
using namespace std;
int result(int n) {
int res;
if (n == 0) {
res = 1;
}
else if (n == 1) {
res = 0;
}
else if (n == 2) {
res = 3;
}
else if (n == 3) {
res = 0;
}
else {
res = 4 * result(n-2) - result(n-4);
}
return res;
}
int main() {
int n;
while (cin >> n && n != -1) {
int res = result(n);
cout << res << endl;
}
return 0;
}
方法不是特別好，請諒解秃踩。
