天涯头条

动态规划——数位DP 学习笔记

2023-09-26 17:47 由 RainPPR 发表于 #其他

动态规划——数位DP 学习笔记

定义

引入

数位 DP 往往都是这样的题型：给定一个区间 \([l, r]\)，求这个区间中满足某种条件的数的总数。

简单的暴力代码如下：

int ans = 0;
for(int i = l; i <= r; ++i)
    if(check(i)) ++ans;

而当数据规模过大，暴力枚举就 \(\mathbb T\) 飞了，因此引入数位 DP：

概念

数位（digit）：对于十进制，即把一个数字按照个位、十位、百位等，一位一位地拆开，它每一位上的数字，也就是 \(0 \sim 9\)；其他进制可类比十进制。

数位 DP：一种按照数位暴力枚举的方式，用来解决一类特定问题；这种问题比较好辨认，一般具有这几个特征：

  1. 提供一个数字区间（有时也只提供上界）来作为统计的限制；
  2. 统计满足某种条件的数的数量，有时也有统计总和、平方和等的；
  3. 上界很大，甚至会有 \(10^{18}\) 这么大，暴力枚举验证会超时；
  4. 这些条件经过转化后可以使用「数位」的思想去理解和判断。

原理

例如，当我们在数数的过程中，\(100 \sim 199\) 和 \(200 \sim 299\) 这两部分，后两位是完全相同的，这种重复计算可以通过 DP 的方式进行优化。

实现

计数原理

数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减，即查分的思路：

$ans_{[l, r]} = s_r - s_{l - 1}$.

一般根据是否计入 \(0\) 的贡献，将 \(s_k\) 定义为：\(\sum[0, k]\) 或 \(\sum[1, k]\).

数的存储

一般将数字中较低位存在数组的低位之中，即：

typedef long long ll;
ll solve(ll x) {
    int len = 0;
    while (x) a[++len] = x % 10, x /= 10;
    return dfs(...); //记忆化搜索
}

常用形参

统计答案可以选择记忆化搜索，也可以选择循环迭代递推；因为数位 DP 的预处理一般比较变态，所有我一般使用记忆化搜索。

常用的形式参数如下：

  1. pos（int）：表示当前枚举的位置，一般从 \(\mathrm{len}\) 开始，到 \(0\) 为止。
  2. limit（bool）：表示当前枚举到的位置，可以填的数是否收到限制；若为 true，则该位最大填 \(a_{pos}\)；否则最大填 \(R-1\)，其中 \(R\) 表示枚举的进制数。
  3. sum（int）：表示从 \(\mathrm{len}\) 到 \(pos + 1\) 位的贡献，常用的有求和等。
  4. last（int）：表示上一位填的数，当题目限制连续的两个（或多个）数位有条件限制的话常用。
  5. lead0（bool）：表示从 \(\mathrm{len}\) 到 \(pos + 1\) 是否都为 \(0\)（前导零）。
  6. r（int）：表示从 \(\mathrm{len}\) 到 \(pos + 1\) 这个前缀模一个数 \(\bmod\) 的结果，也可以表示数位和取模的结果。
  7. st（bool）：常用与状态压缩，其二进制表示某一位是否满足某一条件等。

如何复用结果

简单分析可知，一定是已经求解过中，状态与当前状态相同的，可以复用，如 pos、sum、last 相同等；特殊的，当 limit == 1 或 lead0 == 1 时，即当前位受到限制时，无需记录状态，因为这一状态不会频繁的复用，这种空间换时间价值不大。

即：

typedef long long ll;
ll f[N][M]; // DP 数组，第一维表示枚举到的数位，第二维表示当前的状态；默认为 -1
ll dfs(int pos, bool limit, int sum) {
    if (!pos) return sum;
    if (!limit && f[pos][sum] != -1) return f[pos][sum];
    int up = limit ? a[pos] : 9;
    ll res = 0; for (int i = 0; i <= up; ++i)
        res = (res + dfs(pos - 1, limit && i == up, sum + i)) % MOD;
    if (!limit) f[pos][sum] = res;
    return res;
}

习题

见：https://www.luogu.com.cn/training/384691

Reference

[1] https://oi-wiki.org/dp/number/
[2] https://blog.csdn.net/hzf0701/article/details/116717851
[3] https://blog.csdn.net/m0_63726942/article/details/127060217

热门相关：嫁偶天成   隐婚试爱：娇妻，好甜！   嫡嫁千金   紫府仙缘   上将大叔，狼来了！