暴力搜索

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

// 返回 0~x 中符合要求的数的数量
int len, d[15];
int f[15][10][2][2];
int dfs(int now, int pre, bool limit, bool zero)
{
    if (now == 0)
        return 1;
    int up = limit ? d[now] : 9;
    int res = 0;
    for (int num = 0; num <= up; num++)
    {
        if (!zero && abs(num - pre) < 2)
            continue;
        res += dfs(now - 1, num, limit && (num == d[now]), zero && num == 0);
    }
    return res;
}
int cal(int x)
{
    len = 1;
    d[len] = x;
    while (d[len] >= 10)
    {
        d[len + 1] = d[len] / 10;
        d[len] = d[len] % 10;
        len++;
    }
    return dfs(len, 0, true, true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B;
    cin >> A >> B;
    cout << cal(B) - cal(A - 1);
    return 0;
}

记忆化搜索

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

// 返回 0~x 中符合要求的数的数量
int len, d[15];
int f[15][10][2][2];
int dfs(int now, int pre, bool limit, bool zero)
{
    if (f[now][pre][limit][zero] != -1)
        return f[now][pre][limit][zero];
    if (now == 0)
        return f[now][pre][limit][zero] = 1;
    int up = limit ? d[now] : 9;
    int res = 0;
    for (int num = 0; num <= up; num++)
    {
        if (!zero && abs(num - pre) < 2)
            continue;
        res += dfs(now - 1, num, limit && (num == d[now]), zero && num == 0);
    }
    return f[now][pre][limit][zero] = res;
}
int cal(int x)
{
    len = 1;
    d[len] = x;
    while (d[len] >= 10)
    {
        d[len + 1] = d[len] / 10;
        d[len] = d[len] % 10;
        len++;
    }
    memset(f, -1, sizeof(f));
    return dfs(len, 0, true, true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B;
    cin >> A >> B;
    cout << cal(B) - cal(A - 1);
    return 0;
}

更常写的记忆化搜索

一般更常见的是只记忆 limit、zero 都是假的情况。

#include <bits/stdc++.h>
using namespace std;
int L, R;
int dp[15][10];  // 记忆化搜索 dp[pos][pre]
int d[15], dlen; // d[dlen]~d[1]
// 做到了第 pos 位，前一位是 pre，是否顶到了上限，之前是否都填的 0
int dfs(int pos, int pre, bool limit, bool zero)
{
    if (pos == 0)
        return 1;
    // 算过了没贴边的结果的话就直接返回
    if (!limit && !zero && dp[pos][pre] != -1)
        return dp[pos][pre];
    // 当前这一位的上限
    int up = limit ? d[pos] : 9;
    int sum = 0;                        // 记录方案数
    for (int now = 0; now <= up; now++) // 枚举当前这一位
    {
        if (zero) // 当前是第一个数，前面都是前导 0
        {
            // 第一个数没有差至少为2的限制
            sum += dfs(pos - 1, now, limit && now == d[pos], zero && now == 0);
        }
        else
        {
            if (abs(now - pre) < 2)
                continue;
            sum += dfs(pos - 1, now, limit && now == d[pos], zero && now == 0);
        }
    }
    // 如果前面没贴边，就记忆化一下
    if (!limit && !zero)
        dp[pos][pre] = sum;
    return sum;
}
int cal(int x)
{
    if (x == 0)
        return 1;
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    return dfs(dlen, 0, true, true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> L >> R;
    memset(dp, -1, sizeof(dp));
    cout << cal(R) - cal(L - 1) << "\n";
    return 0;
}