<递推>hdoj 2569 彼岸

一开始想运用高中黄老师教的排列组合知识来做哈哈哈，忽然很想念数学老师。
他真是一位非常优秀的老师啊，当时不自知。哦最后当然wa了，递推式了解一下？

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2569

题目大意：
悬崖，n，每三个格子的颜色不能完全不相同，否则就掉下悬崖啦。
n个格子的悬崖，有多少种放颜色的可能呢？

解题思路：
珠子，我们来抽象一下，取里边某三个珠子，后边递推就行。

//第i块，第i-1块，第i-2块
如果第一块和第二块颜色相同，
那么第三块的颜色的数目等于第一块颜色的数目乘以三

如果第一块和第二块颜色不同，
那么第三块的颜色的数目等于第二块的颜色的数目减去第一块颜色的数目,得到的差乘以2
（Q1:为什么乘以2？）
A:因为第三块的颜色不是和第一块相同就是和第二块相同，有两种可能性
（Q2:为什么要拿第二块颜色的数目减去第一块颜色的数目？）
A:因为第二块颜色的数目本身，包含了和第一块颜色相同的第二块颜色的数目，
需要把这部分剪掉，而颜色相同时，数目当然也相等啦

综上，第三块颜色数目的总可能性=step[i]=step[i-2]3+(step[i-1]-step[i-2])2

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n;            //(n<40)
    cin>>t;
    
    int step[50]={0,3,9,21};
    for(int i=3;i<50;i++)
        step[i]=step[i-1]*2+step[i-2];
    
    while(t--)
    {
        cin>>n;
        cout<<step[n]<<endl; 
    }
    return 0;
    
}