不容易系列之(3)—— LELE的RPG难题

有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

思路：运用递归算法。

         a[1]=3,a[2]=6,a[3]=6

         分两种情况讨论：

         第一种：第（n-1）个格子与第一个格子不同色，那么涂（n-1）个格子共有a[n-1]种方法，由于（n-1）格子与第一个格子不同色，最后一格子只有一种颜色可涂。

         第二种：第（n-1）个格子与第一个格子同色，前面的（n-2）个格子共有a[n-2]种凃法，加上的（n-1）个格子由于与第一个格子同色，所以不会与（n-2）个格子                       颜色相同，此时最后一个格子有两种凃法，所有共有2*a[n-2]方法。

         总和：a[n]=a[n-1]+2*a[n-2]

#include <iostream>
using namespace std;
int main()
{
    long long a[100];
    a[1] = 3;
    a[2] = 6;
    a[3] = 6;
    int n;
    while (cin>>n)
    {
        for (int i=4; i <= n; i++)
        {
            a[i] = a[i - 1] + 2 * a[i - 2];
        }
        cout << a[n] << endl;
    }
}