数位$\textbf{dp}$的特征是：要求计算$[L,R]$区间内符合要求的数。

（例题：P2657）

用$f[i][j]$保存从前往后考虑到第$i$个数位，前缀为$j$情况下的答案。很明显，我们要枚举数位来进行计算。

核心转移方程是：

$$f(i,pre,equal)=\sum_{i=1}^{up}f(i+1,k,equal \ \& \ (i==limit))$$ 在这道题当中，$k$需要满足$\left| k-i\right|\ge2$。

需要注意的是$\quad equal \ and \ i==limit\quad$这句话，如果之前的数位都被限制，并且当前数位也被限制，那么下一个数位也会受限制，否则不会受限制。因为位数相同的情况下，如果一个数$A$比另一个数$B$小，那么从最高位开始比较，第一个不相同的数位$A$一定比$B$小。

还有这句话：

if(pre == 11 && i == 0)
    ans += dfs(x - 1, 11, equal && (i == limit));
else
    ans += dfs(x - 1, i, equal && (i == limit));

也非常坑，需要注意的是当$pre=11$且$i=0$的时候，下一次搜索的$equal$才等于$11$。这也就是处理前导$0$，只要当前位数之前存在一个数位，那么$limit$就不可能为$11$，因此在枚举数位枚举到$0$的时候，如果这个$0$依然是前导$0$，那么就将$limit=11$继续传到下去，然后再记忆化搜索即可。

其他的根据实际情况写就可以了。

完整代码

#include<bits/stdc++.h>
using namespace std;

int f[15][15];
vector<int> digit;

inline long long dfs(int x, int pre, int equal) {
    if(!x)
        return 1;
    if(!equal && ~f[x][pre])
        return f[x][pre];
    int limit = equal ? digit[x] : 9;
    long long ans = 0;
    for(register int i = 0; i <= limit; i++)  {
        if(abs(i - pre) < 2)
            continue;
        if(pre == 11 && i == 0)
            ans += dfs(x - 1, 11, equal && (i == limit));
        else
            ans += dfs(x - 1, i, equal && (i == limit));
    }
    if(!equal)
        f[x][pre] = ans;
    return ans;
}

inline long long solve(int x) {
    memset(f, -1, sizeof(f));
    digit.clear();
    digit.push_back(-1);
    while(x) {
        digit.push_back(x % 10);
        x /= 10;
    }
    return dfs(digit.size() - 1, 11, 1);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << solve(b) - solve(a - 1);
    return 0;
}

例题 P2602

搜索的时候需要记录当前是否含有前导零，且$f(x,\,pre,\,equal,\,has\_zero)$表示的是意思是 “当前在第$x$位上，前缀状态数为$pre$，是否与当前数字保持相等，是否含有前导零” 的情况下的状态数。

注意！

判断$x$不是$-1$的方法是$\sim x$，不能打$!\sim x$。

被坑很多次了！

#include<bits/stdc++.h>
using namespace std;

long long f[15][15][2][2];
int digit[15], len = 0;

inline long long dfs(int x, int pre, int now_d, bool equal, bool has_zero) {
    if(x <= 0)
        return pre;
    if(~f[x][pre][equal][has_zero])
        return f[x][pre][equal][has_zero];
    long long res = 0;
    int limit = equal ? digit[x] : 9;
    for(register int i = 0; i <= limit; i++)
        res += dfs(x-1, pre+((!has_zero||i) && (i==now_d)), now_d, equal&&(i==limit), has_zero&&(i==0));
    return f[x][pre][equal][has_zero] = res;
}

inline long long solve(long long x, int now_d) {
    memset(f, -1, sizeof(f));
    for(len = 0; x; x /= 10)
        digit[++len] = x % 10;
    return dfs(len, 0, now_d, 1, 1);
}

int main() {
    long long x, y;
    scanf("%lli %lli", &x, &y);
    for(register int i = 0; i <= 9; i++)
        printf("%lli ", solve(y, i) - solve(x-1, i));
}