链接：https://ac.nowcoder.com/acm/contest/74784/1002 来源：牛客网

作为队伍的核心，forever97很受另外两个队友的尊敬。 Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。 如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。 但是forever97又不喜欢连续三天吃一种外卖。 如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。 作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？

题目大意：不能连续三天选同一家店，问选法数量

类似与斐波那契，只是加了限制条件

## 第一次的尝试 想了好久，第一次通过递推第三项尝试了一个非常不周全的方法

 dp[i][1]=((dp[i-1][1]*(dp[i-2][3]+dp[i-2][2]))%mod+(dp[i-1][2]*(dp[i-2][3]+dp[i-2][2]+dp[i-2][1]))%mod+(dp[i-1][3]*(dp[i-2][3]+dp[i-2][2]+dp[i-2][1]))%mod)%mod;
            dp[i][2]=((dp[i-1][2]*(dp[i-2][3]+dp[i-2][1]))%mod+(dp[i-1][1]*(dp[i-2][3]+dp[i-2][2]+dp[i-2][1]))%mod+(dp[i-1][3]*(dp[i-2][3]+dp[i-2][2]+dp[i-2][1]))%mod)%mod;
            dp[i][3]=((dp[i-1][3]*(dp[i-2][1]+dp[i-2][2]))%mod+(dp[i-1][2]*(dp[i-2][3]+dp[i-2][2]+dp[i-2][1]))%mod+(dp[i-1][1]*(dp[i-2][3]+dp[i-2][2]+dp[i-2][1]))%mod)%mod;
        }
        cout<<dp[x][1]<<"\n";
    }
}

很长的代码，简言之就是认为是这个关系

3-1-1  2-1-1
1-3-1  3-3-1 2-3-1 
2-2-1  3-2-1 1-2-1

简单在递推结果上就写出了代码

但是应该想到，以上述代码中，i选1时，dp[i][1]=((dp[i-1][1]*(dp[i-2][3]+dp[i-2][2]))，第i-1如果选了1，dp[i-2]中也能选1,这样三者就重和，不符合题意。

看了题解后的下一次尝试

for(int i=3;i<N;i++){
        f[0][i]=(f[0][i-1]+f[1][i-1]+f[2][i-1]+f[2][i-2]+f[1][i-2])%mod;
        f[1][i]=(f[1][i-1]+f[1][i-1]+f[2][i-1]+f[2][i-2]+f[0][i-2])%mod;
        f[2][i]=(f[2][i-2]+f[1][i-1]+f[2][i-1]+f[0][i-2]+f[1][i-2])%mod;
    }

因为我也想到了最开始的代码出现了三者重合。然后，为了避免少去连续两次的情况，如1 1 2，所以第二天我也加上了f[1][i-1].答案错误。仔细思考，发现

按周期，第i天选的1，第i-1,i-2都不能 因为如第i-1选的2，在前面也计算过i-2的1，第i-2的2也计算过i-3的1，如果选了1，i-1,i-2,i-3就会有3个1 三个状态相互制约和递推，就能形成正确答案

最后写出的的正确代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=120000,mod=1e9+7;
int f[3][N];
signed main(){
    int T;
    cin>>T;
    f[0][0]=f[1][0]=f[2][0]=0;
    f[0][1]=f[1][1]=f[2][1]=1;
    f[0][2]=f[1][2]=f[2][2]=3;
    for(int i=3;i<N;i++){
        f[0][i]=(f[1][i-1]+f[2][i-1]+f[2][i-2]+f[1][i-2])%mod;
        f[1][i]=(f[1][i-1]+f[2][i-1]+f[2][i-2]+f[0][i-2])%mod;
        f[2][i]=(f[1][i-1]+f[2][i-1]+f[0][i-2]+f[1][i-2])%mod;
    }
    while(T--){
        int n;
        cin>>n;
        cout<<(f[0][n]+f[1][n]+f[2][n])%mod<<"\n";
    }
}

(当然还有更高效（空间上）的思考方式，后续可以自行搜索题解)