数位DP

数位 DP 在解决什么

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

常见题目会问：

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

这些题的共同点是：如果直接枚举 1∼n1 \sim n，数字太多；但如果把一个数拆成十进制数位，从高位到低位填写，每一位只有 0∼90 \sim 9 十种选择。真正复杂的地方不是选择数字，而是如何处理“不超过 nn”这个上界。

所以数位 DP 的核心套路是：

  1. 写一个函数 solve(n)，表示统计 [1,n][1,n] 内的合法数字个数。
  2. 区间答案转成前缀差：
ans(L,R)=solve(R)−solve(L−1) ans(L,R)=solve(R)-solve(L-1)
  1. 在 solve(n) 内，把 nn 拆成数位，然后从高位到低位做搜索或递推。

例题：windy 数

luogu-P2657

不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。给定 a,ba,b，求 [a,b][a,b] 中有多少个 windy 数。

例如：

  • 135135 是 windy 数，因为 ∣1−3∣≥2|1-3| \ge 2 且 ∣3−5∣≥2|3-5| \ge 2。
  • 123123 不是 windy 数，因为 ∣1−2∣<2|1-2| < 2。
  • 102102 不是 windy 数，因为 ∣1−0∣=1|1-0|=1。
  • 一位数 1∼91 \sim 9 都是 windy 数。

这个题目非常适合入门数位 DP，因为它只需要记录上一位数字。

把数字看成一棵搜索树

假设我们要统计不超过 n=357n=357 的 windy 数。

从高位开始填数：

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

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

也就是说，每走到搜索树上的一个点，我们需要知道四件事：

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

这四个量就是递归版数位 DP 的状态。

limit 和 lead

数位 DP 最容易混乱的就是 limit 和 lead。

limit：是否贴着上界

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

cpp
copy 
        
1
2

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

如果当前位选择了 i，那么下一层是否继续贴着上界，取决于：

limitnext=limit∧(i=num[pos]) limit_{next}=limit \land (i=num[pos])

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

lead：是否仍是前导零

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

如果当前位选择了 i，那么下一层是否仍是前导零，取决于：

leadnext=lead∧(i=0) lead_{next}=lead \land (i=0)

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

DFS 状态设计

定义：

cpp
copy 
        
1
2

        dfs(pos, last, limit, lead)

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

边界：

cpp
copy 
        
1
2

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

含义是：

  • 如果所有位都填完了，并且 lead == true，说明整个数都是前导零，也就是数字 00。题目只统计正整数，所以返回 0。
  • 否则，已经形成了一个合法正整数，返回 1。

转移时枚举当前位 i：

cpp
copy 
        
1
2
3
4
5

        int up = limit ? num[pos] : 9;
for (int i = 0; i <= up; i++) {
    ...
}

分两种情况：

  1. 如果 lead == true，说明前面还没有真实数字。当前位可以继续填 0，也可以填 1..9 开始一个数字，不需要检查 abs(i-last)。
  2. 如果 lead == false，说明前面已经有真实数字。当前位必须满足 abs(i-last) >= 2。

核心转移：

cpp
copy 
        
1
2
3
4
5
6
7
8

        if (lead) {
    res += dfs(pos - 1, i, limit && (i == num[pos]), lead && (i == 0));
} else {
    if (abs(i - last) >= 2) {
        res += dfs(pos - 1, i, limit && (i == num[pos]), false);
    }
}

注意：lead == false 时，下一层一定还是 false，因为数字已经开始了。即使当前位填 0，这个 0 也是数字内部的真实 0，不是前导零。

为什么可以记忆化

如果 limit == true，当前状态受上界数字影响。比如同样是 pos=2,last=3，上界剩余是 57 和上界剩余是 99，可选范围不同，答案不同，不能直接缓存。

如果 limit == false，后面的每一位都可以从 0..9 中选。此时答案只和 pos,last,lead 有关。

这题的代码只缓存：

cpp
copy 
        
1
2
3
4

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

为什么还要求 !lead？

因为 lead == true 时，前面还没有真实数字，last 并不代表一个真实的上一位。这个状态下的含义是“还没有开始填数”，和 last=0、last=5 这些数字没有关系。

当然，也可以专门给 lead 增加一维缓存：

cpp
copy 
        
1
2

        dp[pos][last][lead]

但本题里 lead == true 的状态很少，直接不缓存更简单。

递归模板代码

cpp
copy 
        
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

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

int dp[15][20]; 
// dp[pos][last] 表示: 在不贴上界、没有前导零、上一位为 last 时,
// 还剩 pos 位可以填写的合法方案数。

int num[15]; // 数字的拆分

// 从高位到低位填写数字。
// pos: 当前还要填写第 pos 位, num[pos] 是这一位的上界数字。
// last: 上一位已经填的数字。
// limit: 前缀是否仍然贴着上界。
// lead: 前面是否全是前导零。
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 ? num[pos] : 9; //上界
    
    int res = 0;

    for(int i = 0; i<= up;i++)
    {
        if( lead ) {
            res += dfs(pos-1,i,limit && (i == num[pos]), lead && (i == 0) );
        }
        else {
            if( abs(i - last) >=2)
                res += dfs(pos-1,i,limit && (i == num[pos]), lead && (i==0));
              // 这里 lead && (i==0) 一定是 false。
        }

    }

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


}

int solve(int x) {
    if( x == 0) return 0;
    int len = 0;
    while(x) {
        num[++len] = x % 10;
        x /= 10;
    }
    return dfs(len,0,true,true);
}

int main (int argc, char *argv[]) {

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

        int l ,r;
        cin >> l >> r;
        cout << solve(r) - solve(l-1) << endl;
        

    
    return 0;
}

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

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

例如：

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

非递归递推写法

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

先预处理：

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

边界：

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

转移：

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

这里的含义是：如果当前最高位是 j，下一位是 k，只有 ∣j−k∣≥2|j-k|\ge 2 时才能拼接。

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

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

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

递推代码

cpp
copy 
        
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

        /*-------------------------------------------------
 *  windy 数 - 非递归(递推)数位DP
 *  Author:Rainboy
 *  2018-07-08 08:52
 *-------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;


int a,b;

/* f[i][j]: i位数、最高位为j的windy数个数 */
/* 条件: 相邻两位数字差 >= 2 */
int f[12][10] = {0};
int str[100];    /* 拆解后的数字, 低位在前 */
int cnt;         /* 数字位数 */

/* 将 n 拆成数字存到 str[1..cnt), str[1] 为个位 */
/* 例: n=123 -> str[1]=3, str[2]=2, str[3]=1, cnt=4 */
void div(int n){
    cnt = 1;
    if( n == 0) str[cnt] =0,cnt++;
    while( n > 0){
        str[cnt++] = n % 10;
        n = n / 10;
    }
}

/* 预处理 f 表 */
void init(){
    int i,j,k;

    /* 边界: 1位数, 最高位取 0-9 都只有 1 个 */
    for(i=0;i<=9;i++) f[1][i] = 1; 

    /* 递推: 填 i 位数, 枚举第 i 位 j 和第 i-1 位 k */
    for(i=2;i<=11;i++)
        for(j=0;j<=9;j++)
            for(k=0;k<=9;k++)
                if( abs(j-k) >=2)
                    f[i][j] += f[i-1][k];
}


/* 计算 [0, n] 内 windy 数的个数 */
int calc(int n){
    div(n);

    int i,j,k,res = 0;

    /* 1. 位数少于 n 的数 (位数 < cnt-1) */
    /*    最高位不能为 0, 故 j 从 1 开始 */
    for(i=1;i<cnt-1;i++) 
        for(j=1;j<=9;j++)
            res += f[i][j];

    /* 2. 位数与 n 相同, 但最高位 < str[cnt-1] */
    for(i=1;i<str[cnt-1];i++)
        res+= f[cnt-1][i];

    /* 3. 从高位到低位固定前缀, 统计剩余位 */
    for(i=cnt-2;i>=1;i--)
    {
        /* 当前位取 [0, str[i]-1], 且与上一位差 >= 2 */
        for(j=0;j<str[i];j++)
            if( abs(j-str[i+1]) >=2 )
                res += f[i][j];

        /* n 自己的这两位差 < 2, 后续不可能满足, 提前退出 */
        if( abs(str[i] - str[i+1]) < 2)
            break;

        /* 所有位都满足条件, n 本身也是 windy 数 */
        if( i== 1)
            res+=1;
    }
    return res;

}

int main(){
    init();
    scanf("%d%d",&a,&b);
    int ans;
    ans = calc(b) - calc(a-1);
    printf("%d\n",ans);
    return 0;
}

两种写法怎么选

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

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

做题步骤

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

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

一句话总结：数位 DP 不是在枚举每个数，而是在枚举一棵数字前缀树；limit 负责不越过上界，lead 负责正确处理前导零，记忆化负责合并相同的自由子树。