【简单dp】舔狗舔到最后一无所有

舔狗舔到最后一无所有 (nowcoder.com)

题意：

 思路：

设状态dp[i][j]为到第i天，选吃第家外卖的方案数，这样定义的状态是唯一的，因此可以这样定义

然后就可以对第i天吃的啥外卖进行分类讨论

对于dp[i][1]：

第i-1天可能吃1，2，3

如果第i-1天吃2，3，那么对第i-2天无影响

如果第i-1天吃1，那么第i-2天只能吃2或3

因此:

dp[i][1]=dp[i-1][2]+dp[i-1][3]+dp[i-2][2]+dp[i-2][3]

dp[i][2]=dp[i-1][1]+dp[i-1][3]+dp[i-2][1]+dp[i-2][3]

dp[i][3]=dp[i-1][1]+dp[i-1][2]+dp[i-2][1]+dp[i-2][2]

然后对第0天，第1天和第2天初始化即可：

dp[0][1]=dp[0][2]=dp[0][3]=0;

dp[1][1]=dp[1][2]=dp[1][3]=1;

dp[2][1]=dp[2][2]=dp[2][3]=3;

Code：

#include <bits/stdc++.h>
const int mxn=1e5+10,m=1e9+7;
long long dp[mxn][4];
using namespace std;
int main(){
    int t,n,ans;
    dp[0][1]=dp[0][2]=dp[0][3]=0;
    dp[1][1]=dp[1][2]=dp[1][3]=1;
    dp[2][1]=dp[2][2]=dp[2][3]=3;
    for(int i=3;i<mxn;i++){
        dp[i][1]=(dp[i-1][2]+dp[i-1][3]+dp[i-2][2]+dp[i-2][3])%m;
        dp[i][2]=(dp[i-1][1]+dp[i-1][3]+dp[i-2][1]+dp[i-2][3])%m;
        dp[i][3]=(dp[i-1][1]+dp[i-1][2]+dp[i-2][1]+dp[i-2][2])%m;
    }
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d",&n);
        ans=(dp[n][1]%m+dp[n][2]%m+dp[n][3]%m)%m;
        printf("%lld\n",ans);
    }
    return 0;
}