通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 动态规划精讲(二)数位动态规划

174人浏览 / 0人评论 / | 作者:whisper  | 分类: 动态规划  | 标签: leetcode  | 

作者:whisper

链接:https://proprogrammar.com/article/1025

声明:请尊重原作者的劳动,如需转载请注明出处


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

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

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

数位动态规划简介


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

时间复杂度一般是 Llog10​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 状态, 表示高位是否是前导零。

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

力扣上数位 DP 的题目不多,下一节提供了 9 道练习题,可以巩固数位 DP 的思维方式。

数位动态规划练习题


以下 9 道题是力扣上数位 DP 相关的题目。

满足某些条件的数字个数

  • 最大为 N 的数字组合
  • 中心对称数 III
  • 计算各个位数不同的数字个数
  • 不含连续 1 的非负整数
  • 至少有 1 位重复的数字
  • 易混淆数 II

将 x∈[L,R] 代到一个函数 f(x) 中, 一个数字 x 的 f(x) 值为一次贡献的量, 求总的贡献

  • 数字 1 的个数
  • 范围内的数字计数
  • 2 出现的次数

亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告