对拍了一下，刚开始wa了一次
这是要求处理没有前导0的，模版，其实就是原来的！limit的地方再加上！lead（就这里wa了一次）还有再加一个lead的参数就可以了，当lead为0时表示开始的情况，不要有限制，因为开始是随意的。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; ll f[20][12]; int n,m,li[12]; ll dfs(int i,bool lead,int state,bool limit) { if (i==0) return 1; if (!limit && !lead && f[i][state]!=-1) return f[i][state];//这里就是说lead和limit的情况要特殊计算 int up=limit ? li[i]:9; ll ans=0; for (int j=0;j<=up;j++) if (lead||abs(state-j)>=2) { ans+=dfs(i-1,lead && j==0,j,limit && j==up); } if (!limit && !lead) f[i][state]=ans; return ans; } ll work(ll n) { memset(f,-1,sizeof(f)); memset(li,0,sizeof(li)); int tot=0; while (n) { li[++tot]=n%10; n=n/10; } return dfs(tot,true,0,true);//前导为0，所以上一个state也为0 } int main() { scanf("%lld%lld",&n,&m); printf("%lld",work(m) -work(n-1)); return 0; }
