动态规划（选择）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

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

---

分析：

可以重复，也可以不重复，可以弄一个维度，表明与上一个重复或者不重复。

所以本位重复，那么上一位就不能重复，两者等价。

如果本为不重复，那么上一位可以重复或者不重复，所以等于（重复+不重复）*两种可能

---

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll mod=1e9+7;
void solve()
{ll n;cin>>n;ll dp[n+1][3];memset(dp,0,sizeof dp);if(n==1){cout<<3<<'\n';return ;}else if(n==2){cout<<9<<'\n';return ;}else{dp[2][0]=6,dp[2][1]=3;for(ll i=3;i<=n;i++){dp[i][0]=(dp[i-1][1]%mod+dp[i-1][0]%mod)*2%mod;dp[i][1]=dp[i-1][0];}cout<<(dp[n][0]+dp[n][1])%mod<<'\n';return ;}
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t=1;cin>>t;while(t--)solve();return 0;}