我的算法书 - 数位DP

一句话算法

数位 DP 不是枚举每个数，而是从高位到低位枚举数字前缀；limit 保证不超过上界，lead 保证前导零不被当成真实数字。

问题模型

数位 DP 解决的是一类按数位限制来计数的问题。

常见题面会问：

$[L,R]$ 中有多少个数满足某种性质；
不超过 $n$ 的数中，有多少个数不含某个数字；
不超过 $n$ 的数中，有多少个数的相邻数位满足某个关系；
不超过 $n$ 的数中，有多少个数的数位和、模数、出现次数满足限制。

这些题的共同点是：直接枚举 $1 \sim n$ 太慢，但把一个数拆成十进制数位后，每一位只有 $0 \sim 9$ 十种选择。真正困难的地方不是“这一位能填什么数字”，而是“填完之后是否仍然不能超过上界”。

所以数位 DP 通常先写前缀统计函数：

solve(n)=\text{统计 }[1,n]\text{ 内合法数字个数}

区间答案再转成前缀差：

ans(L,R)=solve(R)-solve(L-1)

本文用 luogu-P2657 windy 数作为主例。

windy 数定义：不含前导零，且相邻两个数字之差至少为 $2$ 的正整数。

例如：

$135$ 是 windy 数，因为 $|1-3| \ge 2$ 且 $|3-5| \ge 2$ 。
$123$ 不是 windy 数，因为 $|1-2| < 2$ 。
$102$ 不是 windy 数，因为 $|1-0|=1$ 。
一位数 $1 \sim 9$ 都是 windy 数。

给定 $a,b$ ，求 $[a,b]$ 中有多少个 windy 数。

核心直觉

把所有不超过 $n$ 的数字看成一棵从高位往低位填写的搜索树。

假设要统计不超过 $357$ 的 windy 数：

第 1 位: 0 1 2 3
第 2 位: 根据第 1 位和上界继续选择
第 3 位: 根据第 2 位和上界继续选择

如果第一位填 1 或 2，前缀已经小于 357，后面的位可以在 0..9 中自由选择。
如果第一位填 3，前缀仍然贴着上界，第二位最多只能填 5。
如果第一位填 0，这表示数字还没有真正开始，仍然处于前导零状态。

因此递归版数位 DP 的状态需要记住四类信息：

pos：当前还剩多少位要填。
last：上一位真实填下去的数字。
limit：前缀是否仍然贴着上界。
lead：前面是否全是前导零。

其中 limit 和 lead 是数位 DP 最容易混乱的两个标记。

`limit`：是否贴着上界

limit == true 表示前面填出的前缀与 $n$ 的前缀完全相同，所以当前位不能超过 $n$ 的当前位。

cpp

        1

        int up = limit ? digit[pos] : 9;

当前位选择 cur 后，下一层是否继续贴着上界，取决于：

limit_{next}=limit \land (cur=digit[pos])

只要某一位填得比上界小，后面所有位都不再受上界限制。

`lead`：是否仍是前导零

lead == true 表示前面填的全是 0，还没有开始形成一个正整数。

当前位选择 cur 后，下一层是否仍是前导零，取决于：

lead_{next}=lead \land (cur=0)

在 windy 数里，前导零不参与“相邻数字差至少为 $2$ ”的判断。例如数字 $7$ 在三位视角下可以写成 007，但不能因为 0 和 7 相邻就判断 $|0-7|$ 。前导零只是占位，不是数字本身的一部分。

算法步骤

记忆化 DFS 写法：

写 solve(n)，将 $n$ 的十进制数位拆到 digit[]。
从最高位开始调用 dfs(pos, last, limit, lead)。
在 dfs 中枚举当前位 cur，上界为 limit ? digit[pos] : 9。
如果仍处于 lead，当前位可以继续填 0，也可以填 1..9 开始数字，不检查相邻差。
如果已经不是 lead，当前位必须满足 abs(cur - last) >= 2。
当 pos == 0 时，若仍是 lead，说明得到的是数字 $0$ ，本题不统计；否则得到一个合法正整数。
只有在 !limit && !lead 时缓存 dp[pos][last]，因为此时后缀已经完全自由，且 last 是真实上一位。

状态含义：

cpp

        1

        dfs(pos, last, limit, lead)

表示当前还要填写 pos 位，上一位真实数字是 last，当前前缀是否贴着上界为 limit，是否仍处于前导零状态为 lead 时，后面能形成多少个合法 windy 数。

边界：

cpp

        1

        if (pos == 0) return lead ? 0 : 1;

核心转移：

cpp

        1
2
3
4
5
6
7
8
9
10
11

        int up = limit ? digit[pos] : 9;
for (int cur = 0; cur <= up; ++cur) {
    bool next_limit = limit && (cur == digit[pos]);
    bool next_lead = lead && (cur == 0);

    if (lead) {
        res += dfs(pos - 1, cur, next_limit, next_lead);
    } else if (abs(cur - last) >= 2) {
        res += dfs(pos - 1, cur, next_limit, false);
    }
}

注意：lead == false 后，即使当前位填 0，这个 0 也是数字内部的真实 0，不是前导零。

算法证明

核心不变量： dfs(pos, last, limit, lead) 只统计所有与当前前缀一致、还剩 pos 位可填的合法后缀。

证明按搜索树理解最自然：

不重不漏枚举。 每个不超过 $n$ 的非负整数，都对应搜索树中唯一一条从高位到低位的填数路径；每条路径也唯一确定一个数。
上界正确。 若 limit == true，当前位最多填 digit[pos]；若某一位填小了，后面 limit 变为 false，任意填 0..9 都不会超过 $n$ 。
前导零正确。 若 lead == true，前面的 0 只是占位，不参与相邻数位判断；一旦填入非零数字，后续所有位都是真实数字。
windy 条件正确。 当 lead == false 时，last 就是上一位真实数字，转移只保留 abs(cur-last) >= 2 的选择，因此所有保留下来的路径都满足相邻差限制。
边界正确。 pos == 0 时，若仍处于 lead，整条路径表示数字 $0$ ，本题要求正整数所以返回 $0$ ；否则返回 $1$ 。

记忆化也正确：当 !limit && !lead 时，后续每位都可选 0..9，且 last 是真实上一位，所以答案只由 (pos,last) 决定，可以复用。

复杂度分析

设 $D$ 是 $n$ 的十进制位数。

状态数为 $O(D \times 10)$ 。
每个状态枚举 $10$ 个数字。
单次 solve(n) 的时间复杂度为 $O(D \times 10 \times 10)$ ，竞赛中可视为 $O(D)$ 。
空间复杂度为 $O(D \times 10)$ 。

对于 32 位整数， $D \le 10$ ；对于 64 位整数， $D \le 19$ ，数位 DP 的状态规模通常很小。

代码实现

记忆化 DFS 模板

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

// Windy number digit DP.
// A positive integer is windy if the absolute difference between any two
// adjacent digits is at least 2.

int dp[15][10];
int digit[15];

int dfs(int pos, int last, bool limit, bool lead) {
    if (pos == 0) return lead ? 0 : 1;
    if (!limit && !lead && dp[pos][last] != -1) return dp[pos][last];

    int up = limit ? digit[pos] : 9;
    int res = 0;

    for (int cur = 0; cur <= up; ++cur) {
        bool next_limit = limit && (cur == digit[pos]);
        bool next_lead = lead && (cur == 0);

        if (lead) {
            res += dfs(pos - 1, cur, next_limit, next_lead);
        } else if (abs(cur - last) >= 2) {
            res += dfs(pos - 1, cur, next_limit, false);
        }
    }

    if (!limit && !lead) dp[pos][last] = res;
    return res;
}

int solve(int x) {
    if (x <= 0) return 0;

    int len = 0;
    while (x > 0) {
        digit[++len] = x % 10;
        x /= 10;
    }

    return dfs(len, 0, true, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(dp, -1, sizeof(dp));

    int l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << '\n';
    return 0;
}

这份写法是最通用的数位 DP 写法。以后遇到类似题目，通常只需要改两处：

状态里除了 pos,last,limit,lead 之外还要记录什么。
枚举当前位 cur 时，如何判断这个选择是否合法。

例如：

统计数位和，需要增加 sum。
统计模数，需要增加 mod。
禁止出现某个数字，需要在枚举 cur 时跳过它。
禁止出现某个相邻模式，需要记录上一位或前两位。

递推统计模板

对于 windy 数，还可以写成递推。

先预处理：

f[i][j]=i\text{ 位数，最高位为 }j\text{ 的 windy 数个数}

边界：

f[1][0..9]=1

转移：

f[i][j]=\sum_{k=0}^{9} f[i-1][k] \quad (|j-k|\ge 2)

预处理完成后，计算 calc(n)，也就是 $[1,n]$ 的 windy 数个数，分三部分统计：

位数少于 $n$ 的所有 windy 数。
位数等于 $n$ ，但最高位小于 $n$ 最高位的所有 windy 数。
从高位到低位固定前缀，一旦当前位选得比 $n$ 小，后面直接用 f 表统计。

这个思路本质上仍然在走数位搜索树，只是把“不贴上界的子树大小”提前算好了。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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

// Iterative digit DP for Windy numbers.
// f[len][first_digit] = number of len-digit suffixes whose highest digit is
// first_digit and every adjacent digit differs by at least 2.

int f[12][10];

void init() {
    for (int d = 0; d <= 9; ++d) f[1][d] = 1;

    for (int len = 2; len <= 11; ++len) {
        for (int first = 0; first <= 9; ++first) {
            for (int next = 0; next <= 9; ++next) {
                if (abs(first - next) >= 2) {
                    f[len][first] += f[len - 1][next];
                }
            }
        }
    }
}

int calc(int n) {
    if (n <= 0) return 0;

    vector<int> digit(1, 0);
    while (n > 0) {
        digit.push_back(n % 10);
        n /= 10;
    }

    int len = (int)digit.size() - 1;
    int res = 0;

    for (int l = 1; l < len; ++l) {
        for (int first = 1; first <= 9; ++first) {
            res += f[l][first];
        }
    }

    for (int first = 1; first < digit[len]; ++first) {
        res += f[len][first];
    }

    for (int pos = len - 1; pos >= 1; --pos) {
        for (int cur = 0; cur < digit[pos]; ++cur) {
            if (abs(cur - digit[pos + 1]) >= 2) {
                res += f[pos][cur];
            }
        }

        if (abs(digit[pos] - digit[pos + 1]) < 2) break;
        if (pos == 1) ++res;
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int l, r;
    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << '\n';
    return 0;
}

两种写法的选择：

写法	适合场景	优点	缺点
记忆化 DFS	大多数数位 DP 题	状态自然，容易改限制	需要理解 `limit`、`lead`
递推预处理	限制简单、状态少的题	常数小，不用递归	统计 `calc(n)` 的分段逻辑更绕

初学时建议先掌握记忆化 DFS。它和搜索树的关系最直接，也最容易迁移到复杂题目。

测试用例

普通用例：

输入:
1 10

输出:
9

解释： $1 \sim 9$ 都是 windy 数； $10$ 不满足，因为 $|1-0|=1<2$ 。

更适合自测的用例：

输入:
1 20

输出:
17

解释： $1 \sim 9$ 共 $9$ 个；两位数中，10、11、12、21 不合法，13..20 中合法的有 13,14,15,16,17,18,19,20 共 $8$ 个，所以答案是 $17$ 。

边界用例：

输入:
0 0

输出:
0

解释：本题统计正整数， $0$ 不算 windy 数。

应用分类详解

数位 DP 的本质是：按位构造数字，把“是否超过上界”和“当前前缀携带的信息”放进状态里计数。

一、数位禁用与模式限制

典型模式： 题目限制某些数字不能出现，或某些相邻模式不能出现。
识别信号： 题面出现“不含某个数字”“不能出现连续若干位”“相邻数字满足某条件”。
核心建模： 状态记录上一位或有限自动机状态，转移时判断当前数字是否合法。

应用场景	经典题目	核心思路
相邻差限制	luogu-P2657	记录上一位 `last`，要求 `abs(cur-last) >= 2`
禁止数字或子串	hdu-2089	跳过数字 `4`，并记录上一位避免出现 `62`
十进制模式匹配	常见 AC 自动机数位 DP	用自动机状态表示当前前缀匹配到哪里

二、数位和、模数与出现次数

典型模式： 合法性由各位数字的总和、余数、某个数字出现次数决定。
识别信号： 题面出现“各位数字之和”“能被 $m$ 整除”“数字 $d$ 出现了几次”。
核心建模： 状态增加 sum、mod、cnt 等累计量。

应用场景	经典题目	核心思路
数字计数	luogu-P2602	分别统计每个数字在 $[L,R]$ 中出现次数
数位和限制	常见区间计数题	状态记录当前数位和，结束时判断范围
余数限制	常见整除计数题	转移 `next_mod=(mod*10+cur)%m`

三、组合约束计数

典型模式： 数字必须同时满足多种条件，例如数位和、相邻关系、模数、是否含某类数字。
识别信号： 区间范围很大，但数位长度很小；条件只依赖有限历史和累计值。
核心建模： 把所有“未来还需要知道的信息”压进状态，状态规模可控时即可做。

应用场景	经典题目	核心思路
状态压缩数位 DP	不重复数字计数	用 bitmask 记录哪些数字已经出现
双限制计数	数位和加模数	同时记录 `sum` 与 `mod`
进制相关限制	二进制中 1 的个数	按二进制位做同样的 `limit` DP

经典例题

luogu-P2657 windy 数入门题。只需要记录上一位数字，是理解 limit、lead、last 三者关系的最好练习。
hdu-2089 不要 62 经典禁止模式题。不能出现数字 4，也不能出现连续子串 62，状态只需记录上一位是否为 6。
luogu-P2602 数字计数统计 $[a,b]$ 中每个数字出现多少次。它能训练“前缀差”和“前导零不能乱算”的边界处理。
atcoder-abc208_e Digit Products 统计不超过 $n$ 且数位乘积不超过 $k$ 的数。它说明数位 DP 不只记录上一位，也可以记录乘积这类累计状态。

做题步骤

遇到数位 DP，可以按下面的顺序想：

先写 solve(n)，最后答案通常是 solve(r)-solve(l-1)。
把 $n$ 拆成数位，常见写法是低位存在 digit[1]，高位存在 digit[len]。
从高位到低位填写，状态先固定写成 dfs(pos, ..., limit, lead)。
想清楚“判断当前位是否合法”需要知道哪些历史信息，把它们加入状态。
只有在 !limit 时才考虑记忆化；如果 lead 的含义不好缓存，可以先不缓存 lead 状态。
边界处判断是否形成了合法数字。

一句话总结：数位 DP 的难点不是 DP 表有多大，而是状态语义要干净。只要 limit、lead 和“必须记住的历史信息”分清楚，大多数题都能按同一个模板改出来。