数据结构与算法 - 动态规划（数位动态规划）

发表于 2020-10-05 更新于 2021-11-07 分类于数据结构与算法

转载说明

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-2-plus/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

数位 DP 在基础的动态规划问题当中算是比较难的一类，因为数位 DP 的状态的物理意义不太好理解。其它的动态规划，比如区间 DP 状态的物理意义就是区间，状态压缩 DP 中状态的物理意义就是集合，这都比较好理解。

但是数位 DP 比其它 DP 好的一面是数位 DP 的思维相对比较固定。一个是解决的问题模式比较固定，一个是状态设计也比较固定，因此可以通过一些常见问题把数位 DP 的套路了解个大概。

力扣上有几道数位 DP 的题目，通过这些题目我们可以大致了解数位 DP 的思考过程和做法。

数位动态规划简介

数位 DP 主要解决的问题: 在一段区间 [L, R] 上：

满足某些条件的数字个数将 \(x \in [L, R]\) 代到一个函数 \(f(x)\) 中，一个数字 \(x\) 的 \(f(x)\) 值为一次贡献的量，求总的贡献

时间复杂度一般是 \(log_{10}L\)

以一个最简单的例子说明数位 DP 的思考过程：[L, R] 上的整数会共有多少个

首先对于区间 [L, R] 上的问题，首先变成解决前缀 [0, N] 的问题，[0, N] 上的问题解决后，求一次 [0, R] 和 [0, L- 1] 就可以得到原问题的解了。

例如 N = 2357

首先位数的范围是 3 ~ 0，第 3 位为 2，第 2 位为 3，第 1 位为 5，第 0 位为 7。在枚举某个位可能的数字的时候，必须要高位的数字已经确定了，才能只当当前位的枚举范围。

比如当前为是第 2 位，如果它的高位第 3 位是 0、1，则当前第 2 位的选择范围是 0 ~ 9 ；而当第 3 位为 2，第 2 为的选择范围就变成 0 ~ 3 。

分类：高位的数字可以分成两类，如果没有顶到上界（例如第 3 位为 2），则枚举范围就是 0 ~ 9，即不限制，而如果高位顶到了上界（例如第 3 位为 2）当前位的范围就会被限制。

如果当前为枚举的数字因高位顶到了上界而被限制，则当前位的数字枚举也要分类：顶到上界，未顶到上界，这两种对低位的枚举影响不一样

当高位未顶到上界（可能是未被限制，也可能是被限制了但是选的数未顶到上界），则低位的数字无限制，可选 0 ~ 9
当高位顶到了上界，则低位的数字被限制且要分类：顶到上界和未顶到上界

可以看出各个位上未被限制的情况被反复的复用，这是用数位 DP 可以提高效率的地方。而顶到上界的情况，只出现一次

DP 状态设计

dp[pos][lim] ，pos 为当前的数位 N-1 ~ 0 ，lim 表示是否顶到上界，对于 -1 的地方，pos 到 -1 的时候可以 return 1，使得个位的枚举有效。

DP 状态转移

dp[pos][lim]:
dp[pos][0] = 10 * dp[pos - 1][0]
dp[pos][1] = digits[i] * dp[pos - 1][0] + dp[pos - 1][1]

因为顶到上界的时候只需要计算一次，所有 lim 可以不放到 dp 数组里记忆化：将 dp 数组改为 1 维，但是在 dfs 的时候带着 lim 这个参数。

有的时候一串前导 0 需要特别处理。此时可以在 dfs 加一个状态 zero，见后面的例题。

总结

一般数位 DP 的状态必有的维度有 pos、lim
前导零会对结果产生影响时，加一维 zero
可能需要带上前缀的某种状态 state，此状态可能影响当前位的枚举，也可能影响当前位枚举的值对答案的贡献

数位动态规划经典问题

==902. 最大为 N 的数字组合 ==

这道题也是问 [1, N] 上的数字有多少个，只是每一位只能用给定的数字。因此在上面推导过程的基础上，在转移的时候，限制枚举的数字种类即可。

以下为不带前导零状态的数位 dp 模板。

num_set: 可选数字集合
digits[i]: 第 i 位的上界, 在第 i 位若被限制, 则需要取 digits[i]
getdp(...) : dfs

以下为用记忆化搜索进行状态转移的过程，是数位 DP 的代码模板。

其中 pos 表示当前的数位，lim 表示当前是否顶到了上界

int getdp(int pos, int lim, const vector<int>& digits, const set<int>& num_set, vector<vector<int>>& dp)
{
    if(pos == -1) return 1;
    if(dp[pos][lim] != -1)
        return dp[pos][lim];
    dp[pos][lim] = 0;
    int up = lim ? digits[pos] : 9; // 当前要枚举到的上界
    for(int i: num_set) // 枚举当前位所有可能数字
    {
        if(i> up)
            break;
        dp[pos][lim] += getdp(pos - 1, lim && i == up, digits, num_set, dp); // 本位被限制且选顶到上界的数字, 下一位才被限制
    }
    return dp[pos][lim];
}

前导零的分析

增加 zero 状态, 表示高位是否是前导零。

如果高位选了前导零，则当前位无限制，且还可以选前导零。
如果高位没有选前导零且未顶到上界，则当前位在可选数字集合的范围内无限制。
如果高位顶到了上界，则当前位的选择被限制。

数位动态规划练习题

满足某些条件的数字个数
- 最大为 N 的数字组合
- 中心对称数 III
- 计算各个位数不同的数字个数
- 不含连续 1 的非负整数
- 至少有 1 位重复的数字
- 易混淆数 II
将 \(x \in [L, R]\) 代到一个函数 \(f(x)\) 中, 一个数字 \(x\) 的 \(f(x)\) 值为一次贡献的量, 求总的贡献
- 数字 1 的个数
- 范围内的数字计数
- 2 出现的次数

何照江的博客