题意：
一行长度为n的方格，只能使用三种颜色R、P、G来填充，且满足相邻方块不能同色，首尾方块不能同色。给出n，输出满足条件的着色方案数。
思路：
简单递推，由n-1个方块推导出n个方块的情况，有以下两种情况：
1.第n-1个方块与第1个方块不同色，满足条件。直接在n-1的满足基础上添加第n个，且第
n个只有一种选择。即F[n-1]；
2.第n-1个方块与第1个方块同色，不满足F[n-1]，退至F[n-2]，此时添加第n个方块时有两种选择。即F[n-2]*2。
递推公式：F[n] = F[n-1] + 2 * F[n-2]
代码：
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int n; 6 long long f[55]; 7 f[1] = 3; 8 f[2] = 6; 9 f[3] = 6; //注意f[3]不能用递推公式得出 10 for(int i = 4; i < 51; i++) 11 { 12 f[i] = f[i - 1] + 2 * f[i - 2]; 13 } 14 while(cin >> n) 15 { 16 cout << f[n] << endl; 17 } 18 return 0; 19 }
原文：https://www.cnblogs.com/friend-A/p/9691646.html