第三题使用DP过了 dp[i][j] 表示第 i 位以 j 结尾的方案数 cpp代码如下： #include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; const int MAXN = 1e5 + 50; int dp[MAXN][9]; int main(){ for(int i = 0; i < 9; i++) dp[0][i] = 1; for(int i = 1; i < 9; i++) dp[1][i] = 9; dp[1][0] = 8; for(int i = 2; i < MAXN; i++){ for(int j = 0; j < 9; j++){ int cur = j + 1; if(cur != 1){ int num = 0; for(int k = 0; k < 9; k++){ num = (num + dp[i - 1][k]) % MOD; } dp[i][j] = num; }else{ int num = 0; for(int k = 1; k < 9; k++){ num = (num + dp[i - 2][k]) % MOD; } int summ = 0; for(int k = 1; k < 9; k++) summ = (summ + num) % MOD; dp[i][j] = summ; } } } int summ = 0; int n = 0; cin >> n; for(int k = 0; k < 9; k++){ summ = (summ + dp[n - 1][k]) % MOD; } cout << summ << endl; return 0; }