学习笔记：数位 DP

wsy_I · 2026-04-07 20:31:03 · 算法·理论

::::info[致管理大大] 不是，你这让我怎么整改……我是真的不会了。

首先，数学公式中有中文，好吧，这个我改了。

然后，请使用英文定义变量，一看这一大堆 dp2,is0,is3,is4,is8 之类的东西，就真的很不想改，而且我个人感觉也找不到什么用英文改的方法了，而且我感觉明确定义的带有数字的变量还是挺清晰的，难道要改成 dptwo 吗？

最后，逻辑条件请使用集合符号，啊这个……我是要改 \operatorname{otherwise.} 这种东西，还是那一大堆更新的逻辑表达式，例如 up\land[i=a_x] 之类的东西？第一种我感觉改成集合应该更难看吧，然后第二种我是真的想不出来怎么改。

然后我投喂给 AI 的话不仅改了这些东西，改的面目全非，而且改成了一些废话的低质内容，根本没法用。所以求求你给我过吧。真的很绝望。 ::::

往期文章：

学习笔记：状压 DP

\Huge \color{cyan} \colorbox{black} {\textbf{题单}}

理论

数位 DP，通常处理一种统计区间 [l, r] 中满足某些条件的数字个数。这种数据范围一般很大，10^{18} 是比较常见的数字。

在这么大的数据中，直接暴力是不行的，分段打表也不太能处理（不是代码长度爆了就是 TLE），所以我们需要我们今天请出的大杀器——数位 DP。

数位 DP 能够处理的问题一般有以下的特征：

• 可以通过记录这个数的部分信息来表示一个状态。
• 在后面数位做出的选择不会影响在前面数位做出的选择（即 DP 的无后效性）。假如我们发现了有后效性，可以考虑通过增加状态，或者枚举某些变量来满足无后效性。

1. 原理

1.1 递推实现

首先，通过一道你谷上没有的题目引出：

统计 [l, r] 中不含 1 的数字个数。l, r\leq 10^{18}。

数位 DP 的实现有两种方法：递推和记忆化搜索。在本题，我会给出两种方法的代码。

数位 DP 的一个常见转化是通过差分，把 [l, r] 的问题转化为 [1,l-1] 和 [1,r] 的问题。这样可以使得我们的处理方便很多。

接下来想 DP。首先，我们考虑这样一种 DP 的状态：dp_i 表示 i 位的数字可以有多少个 1。其中，这个数字的限制较松：可以有前导零，取值范围为 0\leq x\leq 10^i-1。

首先，我们考虑常规的 DP，即递推。在某一位之后，显然接上任何不含有 1 的数字都可以，所以下一位共有 9 种选择（我们将前导 0 也算入）。于是，我们得到一个朴素的 dp 式子：

但是，可能我们的 l-1 和 r 并不满足可以被表示为 10^i-1 这个性质，所以我们还需要另一个状态，表示在第 i 位之后选满（即令计算数字的后 i 位为 y，那么取值范围为 0\leq x\leq y）可以满足条件的数字个数。我们将这个数组设为 dp2，则有如下转移（设第 i 位的数字为 x）：

可以将这个式子分开理解：第一部分表示这一位为 0 的时候，那么前面就必须按照选满了考虑，因为这一位只能填满。第二部分表示这一位为 1 的时候，由于这里不能选 1，前面一位不会是满的，然而这一位可以取 0，所以从 dp 数组转移。最后一部分就是这一位可以选满，但是也可以不选满。选满即 dp2_{i-1}，不选满的话这一位有 x-1 种选法（本来有 x+1 种，但是 1 和它本身不能选），所以后面的选择可以任意，乘一下即可。

接着，我们考虑边界情况。首先，任意选最后一位的方案数显然是 9，因为可以随便选。对于最后一位选到上界的情况，分讨一下，可以得到 x=0 时最后一位是 1 种方案，否则是 x 种。于是代码就容易写出了：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 18 + 5;
int l, r, dp[N], dp2[N], a[N];

int calc(int x)
{
    if(x == 0) return 1; //这里需要特判，否则会有tot=0
    memset(dp, 0, sizeof dp), memset(dp2, 0, sizeof dp2);
    int tot = 0;
    while(x > 0) //拆位
    {
        a[ ++ tot] = x % 10;
        x /= 10;
    }
    dp[1] = 9;
    if(a[1] == 0) dp2[1] = 1; //初始值
    else dp2[1] = a[1];
    for(int i = 2; i <= tot; i ++ ) //转移，之前已经提到过
    {
        dp[i] = 9 * dp[i - 1];
        if(a[i] == 0)
            dp2[i] = dp2[i - 1];
        else if(a[i] == 1)
            dp2[i] = dp[i - 1];
        else
            dp2[i] = dp2[i - 1] + (a[i] - 1) * dp[i - 1];
    }
    return dp2[tot]; //答案就是最高位的 dp2 值，因为不能超过原数
}

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << endl;
    return 0;
}

1.2 记忆化搜索实现

但是，数位 DP 的递推写法还是太吃操作了，尤其是转移的分类讨论很容易写挂。有没有更加简单强势的做法推荐一下？有的，那就是记忆化搜索。

记忆化搜索的逻辑其实和递推有着很多不同。与递推的按照该位是否取满分类讨论不同，记忆化搜索直接枚举这一位，然后根据是否满足条件选择搜不搜索下一位。接着，对于一些相同且冗余的状态选择使用一个数组记忆化。

记忆化搜索可以如下定义：\operatorname{dfs}(x,up) 表示来到第 x 位，是否顶满这一位为 up。于是，我们可以容易的写出下面的转移方程（使用 a_x 来表示这一位的数字）：

解释一下：方程中的 [] 为艾弗森括号，由于是从高位到低位搜索的，所以下一步的状态为 x-1。后面的这种处理最高位的写法很常用且简洁，不得不说逻辑运算还是太好用了。

接着考虑边界。假如来到了 0，那么前面的所有数都肯定满足（由于我们跳过了选择 1 的情况），所以直接返回 1 即可。记忆化搜索省心的一点就是它不需要考虑边界情况。于是下面的代码容易写出：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 18 + 5;
int l, r, dp[N][2], a[N];

int dfs(int x, bool up)
{
    if(x == 0) return 1; //边界
    if(dp[x][up] ^ -1) return dp[x][up]; //记忆化
    int lim = up ? a[x] : 9, res = 0;
    for(int i = 0; i <= lim; i ++ ) //之前已经提到过了，不多解释
    {
        if(i == 1) continue;
        res += dfs(x - 1, up & (i == lim));
    }
    return dp[x][up] = res; //记忆化
}

int calc(int x)
{
    memset(dp, -1, sizeof dp);
    int tot = 0;
    while(x > 0)
    {
        a[ ++ tot] = x % 10;
        x /= 10;
    }
    return dfs(tot, true);
}

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << endl; 
    return 0;
}

1.3 两种方法的对比

代码长度方面，两种方法差不多。

时间复杂度方面，递推实现是 O(\log_{k}r) 的，而记忆化搜索是 O(k\log_{k}r) 的。（假设数字为 k 进制）所以说记忆化搜索的时间复杂度会劣一点，但是由于 k 一般是常数所以可以接受。

接着是思考难度方面。递推实现需要你想出第一位的边界条件以及如何转移（而且转移方程一般不止一个），而记忆化搜索你只需要考虑边界，其它的直接搜下去就可以了。所以说记忆化搜索要好想很多。

最后是代码是否好背可以复用。递推实现基本上每次换一个题就要改方程，但是记忆化搜索一般只需要改一下参数就可以了，代码大致不变。所以记忆化搜索又胜。

综上所述，记忆化搜索优于递推（虽然你要用递推写也可以），所以以后的代码都会使用记忆化搜索实现。

2. 例题

2.1 有趣数字

求区间 [l, r] 内有多少个数满足这个数的各个数位单调不降。l, r\le 10^{100}。对 10^9+7 取模。

首先看到这么大的数字千万不要先去拿你的高精度板子，因为数位 DP 其实是不需要高精度的。（假如答案不取模当我没说）因为数位 DP 其实是需要先拆位再计算的，你拿一个 string 读进去其实是帮你提前拆好位了。但是我们不能方便的对于字符串做减法，所以可以写一个单点判断 l 是否可行，然后就可以用 [1, r] - [1, l] 来差分了。

接着，我们考虑设计状态。在这里，数字单调不降是相对于它前面的那个数，所以我们还需要额外记录一下前面的那个数，因此定义 \operatorname{dfs}(x,pre,up) 为来到第 x 位，上一位为 pre，是否顶满上界为 up 的数字个数。于是转移显然，枚举下一位大于它即可：

边界也是直接返回 1，因为搜到了那里，就是必定满足性质的。所以代码也很好写出了：

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 100 + 5;
const int MOD = 1e9 + 7;
string L, R;
int a[N], dp[N][N][2];

int dfs(int x, int pre, bool up)
{
    if(x == 0) return 1; //边界 
    if(dp[x][pre][up] ^ -1) return dp[x][pre][up]; //记忆化 
    int lim = up ? a[x] : 9, res = 0;
    for(int i = pre; i <= lim; i ++ )
        res = (res + dfs(x - 1, i, up & (i == lim))) % MOD; //转移 
    return dp[x][pre][up] = res; //记忆化 
}

int calc(string s)
{
    int len = s.size();
    for(int i = 0; i < len; i ++ )
        a[i + 1] = s[i] - '0'; 
    reverse(a + 1, a + len + 1); //由于我习惯高位在后面，所以反转一下 
    memset(dp, -1, sizeof dp);
    return dfs(len, 0, true);
}

int pd(string s) //单点判断 
{
    for(int i = 0; i < s.size() - 1; i ++ )
        if(s[i] > s[i + 1])
            return 0;
    return 1;
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> L >> R;
    cout << (calc(R) - calc(L) + pd(L) + MOD) % MOD << endl; 
    return 0;
}

2.2 windy 数

求区间 [l, r] 内有多少个整数满足相邻两个数字之差至少为 2。l, r\leq 10^{18}。

一个状态多一点的数位 DP 题。话说弱化版我是分段打表的。

这道题，我们需要加入一个数位 dp 的常见操作：记录前导 0。比如前导 0 后面跟着一个 1 是合法的，但是假如不记录前导 0 这种情况就会被错误的舍去。所以我们添加一个变量 is0，假设这一位为 x，那么它的更新方法为 is0\land [x=0]。也就是假如这一位不是前导 0，或者下一位不是 0，下一位就不是前导 0，否则就是。

于是就可以设计状态了。令 \operatorname{dfs}(x,pre,up,is0)，表示来到第 x 位，前一位为 pre，是否顶满上界为 up，是否为前导 0 为 is0。于是，就可以采用以下的方式搜索了。

枚举下一位，如果合法（差值超过 2 或者这一位是前导 0）就搜索下一位转移。还是使用记忆化搜索来做。边界条件也是直接返回 0 即可。代码只给出 dfs 函数。

int dfs(int x, int pre, bool up, bool is0)
{
    if(x == 0) return 1;
    if(dp[x][pre][up][is0] ^ -1) return dp[x][pre][up][is0];
    int lim = up ? a[x] : 9, res = 0;
    for(int i = 0; i <= lim; i ++ )
    {
        if(abs(i - pre) < 2 && !is0) continue;
        res += dfs(x - 1, i, up & (i == lim), is0 & (i == 0));
    }
    return dp[x][pre][up][is0] = res;
}

2.3 手机号码

求区间 [l, r] 内的所有满足如下条件的数：

• 必须是 11 位数。
• 不能同时出现 8 和 4。
• 需要有三个连续且相同的数。

一道状态巨多的数位 DP 题。首先，我们考虑需要维护哪些信息。首先，11 位数的限制是没有用的，因为 l, r 都是 11 位数，一些不合法的答案会被差分掉。然后不能同时出现 8 和 4，所以我们就使用 is4 和 is8 来维护是否出现了 4 和 8。然后前面三个 0 显然是不合法的，所以需要添加一个 is0 来判断前导 0。接着，我们需要维护是否有三个相同的数，这个涉及前两位，所以我们需要 pre 和 pre2 来维护。同时，添加一个 is3 来记录有没有出现过三个相同的数。最后，还是常规的 x 和 up。于是，我们就定义了——

接着，转移还是枚举下一位的数，x, pre, pre2, up, is0 的更新我们在之前已经讲到了，is4 和 is8 的更新如下，假设这一位为 x：is4\vee[x=4], is8\vee[x=8]。可以理解为这一位是这个数字或者前面有这个数字就是真，否则是假。is3 的更新有些许复杂，我们需要判断前面三个是否相同，写成逻辑表达式就是 is3\vee([pre=pre2]\land[x=pre]\land\neg is0)。

边界条件就是假如所有性质就返回 1（is3\land\neg(is4\land is8)），否则返回 0。于是，就容易写出下面的代码了。（还是只给出 dfs 函数部分）：

int dfs(int x, int pre, int pre2, bool up, bool is4, bool is8, bool is3, bool is0)
{
    if(x == 0)
        return (is3 && !(is4 && is8)) ? 1 : 0;
    if(dp[x][pre][pre2][up][is4][is8][is3][is0] ^ -1)
        return dp[x][pre][pre2][up][is4][is8][is3][is0];
    int lim = up ? a[x] : 9, res = 0;
    for(int i = 0; i <= lim; i ++ )
        res += dfs(x - 1, i, pre, up & (i == lim), is4 | (i == 4), 
            is8 | (i == 8), is3 || (pre == pre2 && pre == i && !is0),
            is0 & (i == 0));
    return dp[x][pre][pre2][up][is4][is8][is3][is0] = res;
}

2.4 杠杆数

求 [l, r] 中的杠杆数数量。

杠杆数定义为选择一个数作为支点，两边可以平衡的数，例如 1234 是一个杠杆数，我们取 3 为支点，有 1\times 2+2\times 1=4\times 1。

话说紫题这么水的吗。

首先，我们想一下可不可以一次搜索就搜出来所有的杠杆数。显然这是不太可能的，因为一次搜索在不确定支点的情况下，难以判定一个数是否是杠杆数。

但是，难道这就没有办法了？不是的，我们可以枚举支点！这样的话，问题就变得好做一些了。首先先证明一下对于非 0 的数，假如是杠杆数的话，那么它只有一个支点：

::::info[证明] 首先，这个数非 0，所以在它的支点两边的力矩肯定都非 0。

然后尝试移动这个支点。由于这个数必定左边和右边都有一位非 0，所以假如把这个支点往左移动，那么左边的力矩严格递减，右边的力矩严格递增，必定不平衡。向右移动同理。

故杠杆数只有一个支点。 ::::

我们考虑设计状态。首先，我们需要判定这个数是不是杠杆数，可以设计两个变量 lw, rw 表示杠杆左右两边的力矩，但是这样显然太浪费了。注意到我们可以通过 lw-rw 来衡量这个杠杆是否平衡，所以直接记录差值即可。

接着就是套路了。由于我们枚举了杠杆支点，所以 dp 增加一维记录支点，然后增加一维记录差值。注意到这里有一个 0 的特殊情况，需要注意一下，因为 0 每一位都会被算作一个合法的支点，所以假如两边位数不同，差分的时候就会多出来……解决方法有两种：记录前导 0，或者按照两个数的位数只差减回去。我的代码实现采用记录前导 0。

于是使用 \operatorname{dfs}(x,pos,w,up,is0) 表示来到第 x 位，支点为 pos，两边力矩差值为 w，是否顶满上界为 up，是否是前导 0 为 is0。直接搜索即可。边界条件就是如果 w=0 则构成杠杆数，返回 1，否则返回 0。给出代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 18 + 5;
int x, y, a[N], dp[N][N][2000][2][2];

int dfs(int x, int pos, int w, bool up,bool is0)
{
    if(x == 0)
    {
        if(is0) return 0;
        return w == 0 ? 1 : 0;
    }
    int kw = w + 1000; //力矩可能为负，所以偏移
    if(dp[x][pos][kw][up][is0] ^ -1) return dp[x][pos][kw][up][is0];
    int lim = up ? a[x] : 9, res = 0;
    for(int i = 0; i <= lim; i ++ )
    {
        int nx = x - 1, npos = pos, nw, nup = up & (i == lim), nis0 = is0 & (i==0);
        if(x < pos) nw = w + (pos - x) * i;
        else nw = w - (x - pos) * i;
        res += dfs(nx, npos, nw, nup, nis0);
    }
    return dp[x][pos][kw][up][is0] = res;
}

int calc(int x)
{
    int tot = 0;
    while(x > 0)
    {
        a[ ++ tot] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof dp);
    int ans = 0;
    for(int i = 1; i <= tot; i ++ ) //枚举支点
        ans += dfs(tot, i, 0, true, true);
    return ans;
}

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> x >> y;
    cout << calc(y) - calc(x - 1) << endl;
    return 0;
}

2.5 数字计数

求 [l, r] 中每个数码（0\sim 9）出现了多少次。l, r\leq 10^{12}。

这道题居然是统计每个数码出现的次数，而不是满足条件的数字个数！好吧其实是一样的。

首先，一次搜索求出所有数码很困难，所以我们可以考虑枚举数码然后搜索（反正也要每个数码求一遍）。接着，考虑设计状态。由于这里 0 也要统计出现次数，所以需要记录是否为前导 0，由于前导 0 不算。

于是，设计 \operatorname{dfs}(x,num,cnt,up,is0) 表示来到第 x 位，当前搜索的数字为 num，已经出现了 cnt 次，是否顶满上界为 up，是否为前导 0 为 is0。

于是，具体实现的时候枚举下一位的数字，假设下一位数字为 y，那么下一个 \operatorname{dfs} 状态为 \operatorname{dfs}(x-1,num,cnt+([y=num]\land(\neg is0\vee[y\neq 0]),up\land[y=a_x],is0\land[y=0])。于是直接统计即可。代码实现如下：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 12 + 5;
int l, r, a[N], dp[N][N][N][2][2];

int dfs(int x, int num, int cnt, bool up, bool is0)
{
    if(x == 0) return cnt;
    if(dp[x][num][cnt][up][is0] ^ -1) return dp[x][num][cnt][up][is0];
    int lim = up ? a[x] : 9, res = 0;
    for(int i = 0; i <= lim; i ++ )
    {
        int nx = x - 1, nnum = num, ncnt, nup = up & (i == a[x]), nis0 = is0 & (i == 0);
        ncnt = cnt + ((i == num && !nis0) ? 1 : 0);
        res += dfs(nx, nnum, ncnt, nup, nis0);
    }
    return dp[x][num][cnt][up][is0] = res;
}

int calc(int x, int num)
{
    int tot = 0;
    while(x > 0)
    {
        a[ ++ tot] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof dp);
    return dfs(tot, num, 0, true, true);
}

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> l >> r;
    for(int i = 0; i <= 9; i ++ ) //枚举数码
        cout << calc(r, i) - calc(l - 1, i) << " ";
    return 0;
}

2.6 练习

• 二进制问题
• 烦人的数学作业
• Round Numbers S
• 花神的数论题
• 萌数
• 同类分布
• 如果有别的题可以找我补充。

结语

数位 DP 是一种下限较高，上限不高的 DP 类型，只要熟练了板子，大多数的数位 DP 题都较为简单。个人感觉数位 DP 是很不“DP”的一种 DP，因为 DP 的题目大多都不依赖板子。总之，弄懂了基本原理，数位 DP 就是一个很简单的东西，不要因为题目难度高就觉得它难，其实数位 DP 有很多大水紫。

参考资料：

• 数位 dp