题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1026
比较明显的数位dp，dp[pos][num]表示pos位和上一位数差为num的个数。
初始将num设为-2，然后记忆化开始搜
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const double eps = 1e-8; 5 const ll INF = 9e18 + 7; 6 const int maxn = 5e5 + 10; 7 inline ll read() { 8 ll n = 0, f = 1; char ch = getchar(); 9 while (ch<'0' || ch>'9') { f = -1, ch = getchar(); } 10 while (ch >= '0'&&ch <= '9') { n = n * 10 + ch - '0', ch = getchar(); } 11 return n * f; 12 } 13 int dp[20][12]; 14 int p[20]; 15 int dfs(int pos, int num, int limit) { 16 if (pos == -1) 17 return 1; 18 if (dp[pos][num] != -1 && !limit&&num >= 0) 19 return dp[pos][num]; 20 int up = limit ? p[pos] : 9; 21 int ans = 0; 22 for (int i = 0; i <= up; i++) { 23 if (abs(i - num) < 2)continue; 24 int w = i; 25 if (num == -2 && i == 0) 26 w = num; 27 ans += dfs(pos - 1, w, limit && (i == up)); 28 } 29 if (!limit && !num >= 0) 30 dp[pos][num] = ans; 31 return ans; 32 } 33 int solve(int x) { 34 int pos = 0; 35 while (x) { 36 p[pos++] = x % 10; 37 x /= 10; 38 } 39 return dfs(pos - 1, -2, 1); 40 } 41 int main() { 42 int l, r; 43 l = read(), r = read(); 44 memset(dp, -1, sizeof(dp)); 45 printf("%d\n", solve(r) - solve(l - 1)); 46 //system("pause"); 47 }