第三题使用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; }