乐乐的RPG难题（递推） - HDU 2045
Problem Description
人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即"可乐"）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题: 有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法. 以上就是著名的RPG难题. 如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?
Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。
Output
对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
Sample Input
1
2Sample Output
3
6首先，看到这道题，我们肯定是去想找到它的规律，要不然无从下手。如果你没有想到递推找到规律也是挺难想的，那如果是递推应该是什么规律呢？
核心代码如下：
num[i]=num[i-1]+2*num[i-2];//num[i]代表有i个格对应的涂法 |
|---|
那么为什么如此呢？
首先我们要清楚我们的目的：找到所有种涂法。接下来我们以5个格的情况去举例
第一个格永远不受任何限制，可以取三种，这里以红色为例，那么如果只看前4个格，第四个格只可能为绿和蓝，在这种情况下，如果第4个取绿，第5个只能取蓝一种取法，此时有num[5]=num[4]（即5=4+1的情况下的涂法与4个格涂法相同）
此时还没完，为什么呢？因为情况没有完全取完，第四格由于受第一格约束，不能取红。但实际5个格的话第4个格可以取红。
因此我们在考虑5=3+2，因为此时第一个格已经不能影响第四格了，由于第四个格在上一种情况中已经取绿与蓝了，因此只考虑取红即可。而此时第5个格可取绿与蓝。3格的每种涂法上4,5取红绿或红蓝,即2*num[3]。即num[5]=num[4]+2*num[3]。
那么此时取完了吗，当然，因为第3格在5=4+1情况下不受第一格限制，第2格在任何情况下均受第一格限制，因此，可以肯定所有合法的情况已经取完，且5=4+1,5=3+2情况下因为第4格取颜色不同，因此情况也不会有重复。即为所有涂法。
这样分析以后，我们也就清楚了为什么从4格以后递归，因为只有3格时，2,3格一定会受到第一格影响，情况也只有一种。
同理也可以给出m种颜色下的核心代码：
num[i]=(m-2)*num[i-1]+(m-1)*num[i-2]; |
|---|
代码如下：
#include
using namespace std;
int main()
{
int n;
long long num[55];
num[1]=3;num[2]=6;num[3]=6;
int i;
for(i=4;i<=50;i++)
{
num[i]=num[i-1]+2*num[i-2];
}
while(cin>>n)
{
cout<<num[n]<<endl;
}
return 0;
}