[数据结构与算法]HDOJ 2047阿牛的EOF牛肉串

杭电oj2047阿牛的EOF牛肉串原题链接

题目描述：

思路：

动态规划，最后一位不为O时，有f(n-1)*2种方案；最后一位为O时，倒数第二位不为O，即倒数第二位为E或F，有f(n-2) *2种方案，所以f(n) = f(n-1)*2 + f(n-2) *2

AC代码：

#include <iostream>
using namespace std;
const int N = 45;
long long int dp[N];
int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        dp[0] = 0;
        dp[1] = 3;
        dp[2] = 8;
        for(int i = 3; i <= n;i++)
        {
            dp[i] = 2 * dp[i-1] + 2 * dp[i-2];
        }
            cout << dp[n] << endl;
    }

    return 0;
}