Skip to content

数位 DP

2021-04-02

简介

如何统计区间 [l,r] 中有多少个整数符合某条件?

  1. 暴力算法,枚举 [l,r] 中的每一个整数,逐个判断是否满足条件,遇大数据必 gg。
  2. 优雅地使用 数位 DP

问题

统计区间 [l,r]0l<r100)中有多少整数符合「相邻两个数字之差 2」。

预处理

采用「试填法」:从个位填到最高位,如果第 d 位填了 i,那么第 d+1 位只能填 [0,i2][i+2,9] 中的整数。

f[i,d]:所有最高位为 id 位数中,符合条件的个数。通过给定条件,可以推出:

f[i,d]=|ki|2f[k,d1]
  • 边界条件:f[i,1]=1
  • 计算顺序:f[09,2n]
  • 时间复杂度:O(102logn)
cpp
int f[][];

for (int i = 0; i <= 9; i ++)
    f[i][1] = 1; // 边界条件

for (int d = 2; d <= N; d ++) // N : 位数的上限,N ≈ log(r)
	for (int i = 0; i <= 9; i ++)
		for (int k = 0; k <= 9; k ++)
			if (abs(k - i) >= 2)
				f[i][d] += f[k][d - 1];

数位统计

考虑 前缀和 思想:

dp(n)[0,n] 中有多少个数满足条件。[l,r] 中符合条件的数的个数为 dp(r)dp(l1)

dp(n) 的实现步骤:

step 1

提取 n 每一位上的数字,存入数组 at[ ]

cpp
int cap = 0, at[];
// cap : n 的位数;at[i] : n 的第 i 位数字
while (n)
    at[++ cap] = n % 10, n /= 10;

step 2

所有 1cap1 位数都被包含于 [0,n] 区间中。统计它们中符合条件的个数:

cpp
int ans = 0; // ans : 符合条件的个数
for (int d = 1; d < cap; d ++) // d : 位数
    for (int i = 1; i <= 9; i ++) // i : 最高位填的数
        ans += f[i][d];

step 3

统计所有 cap 位数中符合条件的个数。

使用「试填法」,枚举 d=cap1,从最高位填到最低位,并使填的数 <n

  • d=cap,该位不能填 0,只能填 1at[d]1。统计符合条件的情况;
  • dcap,该位只能填 0at[d]1. 统计符合条件的情况。
    • 若此时 |at[d+1]at[d]|<2,下一位无论怎么填都不符合条件,跳出循环;
    • 若上一步未跳出循环且 d=1,说明 n 本身也符合条件. 但「试填法」最多只填到 n1,故还要多算一个。
cpp
// d : 当前填到第 d 位
for (int d = cap; d >= 1; d --) {
    for (int i = (d == cap); i < at[d]; i ++)
        if (abs(at[d + 1] - i) >= 2)
            ans += f[i][d];
    if (d != cap && abs(at[d + 1] - at[d]) < 2)
        break;
    if (d == 1)
        ans ++;
}

模板

cpp
// 求 [0, n] 中有几个数符合条件
int dp(int n) {
    
    // 特判
    if (n <= 0) return !n;

    int cap = 0, ans = 0, at[];
    while (n)
        at[++ cap] = n % 10, n /= 10;

    for (int d = 1; d < cap; d ++)
        for (int i = 1; i <= 9; i ++)
            ans += f[i][d];
    
    for (int d = cap; d >= 1; d --) {
        for (int i = (d == cap); i < at[d]; i ++)
            if (abs(last - i) >= 2) // 此处条件按照题目的需要
                ans += f[i][d];
        if (d != cap && abs(at[d + 1] - at[d]) < 2)
            break;
        if (d == 1)
            ans ++;
    }

    return ++ ans;
}