文科生的悲哀--简单线性dp易懂

解题思路:
用0表示政治 1表示历史 2表示地理 3表示综合
例如：dp[i][0]就表示第i次考试考的政治的方案数
题目规则转换为：
0后面只能为1
1后面可以为0，2
2后面可以为1，3
3后面只能为2
参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 7654321;
const int N = 10005;
ll n,ans = 0;
int dp[N][5]; 
//例如：dp[i][0]就表示第i次考试考的政治的方案数

void solve(){
    cin>>n;
    memset(dp,0,sizeof(dp));
    dp[1][0] = 1;//初始化第一次考政治为1 
    for(int i = 2;i<=n;i++){
        dp[i][0] = (dp[i-1][1])%mod;//第i次考政治，那么前一次就只能是考历史(只有1后面有0)
        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%mod;//第i次考历史 那么前一次就考政治或者地理 
        dp[i][2] = (dp[i-1][1] + dp[i-1][3])%mod;//第i次考地理 那么前一次就考历史或者综合 
        dp[i][3] = dp[i-1][2]%mod ;//第i次考综合 那么前一次就考地理 
    }
    //n次测试的结果就是第n次考各个科目的总和 
    ans = ((dp[n][0] + dp[n][1])%mod + (dp[n][2] + dp[n][3])%mod)%mod;
    cout<<ans;
}
int main(){ 
    solve();
    return 0;
}