【题目来源】
【题目描述】
给定两个整数 l，r（l≤r），请问 [l, r] 范围内，满足数字的任意相邻两位差值都恰好为 1，且数字至少有两位的数有多少个。
【输入格式】
第一行包含整数 T，表示共有 T 组测试数据。
每组数据占一行，包含两个整数 l 和 r。
【输出格式】
每组数据输出一行，一个结果。
【输入样例】
14 2023
【输出样例】
1
17
【数据范围】
1≤T≤100，
0≤l≤r≤3×10^8
【算法分析】
● 设 f[i][j] 表示长度为 i 最高位为 j 的满足条件的数字个数。
● 由 for(int i=0; i<=9; i++) f[1][i]=1; 知，长度为 1 且分别以 0~9 开头的一位数都满足“任意相邻两位差值都恰好为 1”条件。这看起来似乎难以理解。这是因为，从逻辑上讲，这个条件描述的是“任意两个相邻数字之差为1”。对于一位数来说，它只包含一个数字，不存在“相邻数字”这个概念，因此条件中的前提“相邻”并不成立。在数理逻辑中，一个前提为假的命题，其整体可以被视为真（这在逻辑学中称为“空真”或“虚真”）。所以，在数位DP的初始化中，将一位数视为满足条件是符合常规处理方式的。
● 计算所有长度为 i 最高位为 j 的“相邻数字之差恰好为1”的数字个数。
for(int i=2; i<N; i++) {for(int j=0; j<=9; j++) {if(j==0) f[i][j]=f[i-1][1];else if(j==9) f[i][j]=f[i-1][8];else f[i][j]=f[i-1][j-1]+f[i-1][j+1];}
}
此代码具体含义如下：
当 j==0 时，f[i][j]=f[i-1][1]，因为数字 0 后面只能接数字 1 才能满足相邻数字差为1的条件。
当 j==9 时，f[i][j]=f[i-1][8]，因为数字 9 后面只能接数字 8 才能满足条件。
对于其他数字 j（1 ~ 8），f[i][j]=f[i-1][j-1]+f[i-1][j+1]，因为 j 后面可以接 j-1 或 j+1 来满足条件。
● 在本题的数位 DP 解法代码中，if(n<=0) return 0; 这一边界条件确实至关重要，它确保了程序在处理非正数输入时的正确性。
● 核心逻辑解析
（1）变量初始化
cnt：用于累计符合条件的数字个数。
pre：记录上一位数字的值，初始化为 -1 表示尚未处理任何位。
（2）循环条件与位处理
循环 for(int i=v.size()-1; v.size()>=2 && i>=0; i--) 表示从最高位向最低位遍历数字的每一位。
条件 v.size()>=2 表明此循环仅处理两位数及以上的情况，一位数会通过其他逻辑单独处理。
（3）当前位处理
代码 int x=v[i]; 表示获取当前位的实际值。
代码 int start=(i==v.size()-1)?1:0; 表示确定当前位可以填的数字起始值。如果是最高位，不能为 0，所以 start=1；否则，start=0。
（4）统计当前位小于 x 的情况
for(int j=start; j<x; j++) {if(pre==-1 || abs(pre-j)==1) {cnt+=f[i+1][j];}
}遍历当前位所有小于 x 的可能值 j。
如果 pre==-1（即当前是第一位），或者当前位 j 与前一位 pre 的差值为 1，则这是一个合法的数字开头或延续。
f[i+1][j] 表示以 j 作为当前位，剩余 i+1 位数字的所有合法组合数，并将其累加到 cnt 中。
（5）固定当前位为原数字值 x
if(abs(pre-x)==1 || pre==-1) pre=x;
else break;检查原数字在当前位的值 x 是否与前一位 pre 满足差值条件（或 pre==-1 表示是第一位）。
如果满足，则将 pre 更新为 x，继续处理下一位。
如果不满足，说明原数字 n 本身从这一位开始已经不满足“相邻数字差为1”的条件，后续所有位也必然不满足，因此直接 break 退出循环。
（6）统计原数字 n 本身
if(i==0) cnt++;当循环成功处理到最后一位（i==0）且没有因不满足条件而 break 时，说明原数字 n 本身也满足条件，因此 cnt++。
（7）统计所有位数小于原数字 n 的合法数字个数
for(int i=2; i<=v.size()-1; i++) {for(int j=1; j<=9; j++) cnt+=f[i][j];
}遍历所有可能的数字长度 i（从 2 到 v.size()-1）。
对于每个长度 i，遍历所有可能的最高位 j（从 1 到 9，因为最高位不能为 0）。
累加 f[i][j] 的值到 cnt 中，f[i][j] 表示长度为 i 最高位为 j 的“相邻数字之差恰好为 1”的数字个数。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=12;
int f[N][10]; //f[i][j]表示长度为i最高位为j的满足条件的数字个数void init() {for(int i=0; i<=9; i++) f[1][i]=1;for(int i=2; i<N; i++) {for(int j=0; j<=9; j++) {if(j==0) f[i][j]=f[i-1][1];else if(j==9) f[i][j]=f[i-1][8];else f[i][j]=f[i-1][j-1]+f[i-1][j+1];}}
}int dp(int n) {if(n<=0) return 0; //vipvector<int> v;while(n) {v.push_back(n%10);n/=10;}int cnt=0,pre=-1;for(int i=v.size()-1; v.size()>=2 && i>=0; i--) {int x=v[i];int start=(i==v.size()-1)?1:0;for(int j=start; j<x; j++) {if(pre==-1 || abs(pre-j)==1) {cnt+=f[i+1][j];}}if(abs(pre-x)==1 || pre==-1) pre=x;else break;if(i==0) cnt++;}for(int i=2; i<=v.size()-1; i++) {for(int j=1; j<=9; j++) cnt+=f[i][j];}return cnt;
}int main() {init();int T,le,ri;cin>>T;while(T--) {cin>>le>>ri;cout<<dp(ri)-dp(le-1)<<endl;}
}/*
in:
4
1 10
10 10
1 100
0 300000000out:
1
1
17
1992
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/156048397
https://blog.csdn.net/hnjzsyjyj/article/details/156039366
https://blog.csdn.net/hnjzsyjyj/article/details/156267002
https://blog.csdn.net/hnjzsyjyj/article/details/156011817
https://blog.csdn.net/WhereIsHeroFrom/article/details/148437243
https://www.acwing.com/solution/content/245183/