数位dp总结

「爱情、让人受尽委屈。」 2022-09-14 03:06 179阅读 0赞

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

一般来说数位dp的迭代代码都长下面这样，只是不同的问题处理逻辑不太一样：

if __name__ == "__main__":
        n = 10
        B = 2
        nums = list()
        while n > 0:
            nums.append(n % B)
            n //= B
        # last记录前缀信息, 一般与题目中给定的信息有关
        res, last = 0, 0
        for i in range(len(nums) - 1, -1, -1):
            ...
            if ... : break

一般我们需要记住题目中涉及到的性质：① 包含K个1 ② 不降数 ③ 相邻两个数的差大于等于2 ④ 个数数字之和取模等于0 ⑤ 不包含4与连续的62； 记住这些性质这样我们在遇到类似题目的时候可以反映出怎么样通过递推来预处理二维数组f。数位dp的难点在于预处理，因为预处理本身就是一个dp的过程，一般在考虑状态计算的时候都是枚举最高位和次高位填的数字来计算的。可以发现在状态计算的时候度的数量，数字游戏，数字游戏II和Windy数都是枚举最高位和次高位的数字填什么进行状态计算的。上面的都是数位dp的迭代写法，其实还有一种比较通用的做法是使用dfs来解决，数位dp的dfs写法有一个很大的优点是思维量与代码量都比较小，而且使用记忆化搜索也很快算出来，比较适合于求解比较复杂，涉及到性质比较多的数位dp题目。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9e2e27f256d04352a6ed75f78fe4405d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关数位DP 详解

序 > 天堂在左，战士向右引言数位DP在竞赛中的出现几率极低，但是如果不会数位DP，一旦考到就只能暴力骗分。以下是数位DP详解，涉及到的例题有：

叁歲伎倆/ 2023年08月17日 17:38/ 0 赞/ 68 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 180 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 159 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 255 阅读

相关数位DP UVA - 11038

数位DP，顾名思义，是在个位，十位，百位，千位…….这些数的数位上进行的DP，它其实就是一种暴力枚举+记忆化搜索。数位DP一般用来解决要求找出某个区间内，满足要求的数有多

ゝ一纸荒年。/ 2022年06月09日 00:29/ 0 赞/ 207 阅读

相关 Round Numbers（数位dp）

题目链接： [http://poj.org/problem?id=3252][http_poj.org_problem_id_3252] 分析：本题我一开始思路

墨蓝/ 2022年02月19日 03:39/ 0 赞/ 204 阅读

相关 F(x)(数位dp)

题目链接： [http://acm.hdu.edu.cn/showproblem.php?pid=4734][http_acm.hdu.edu.cn_showproble

青旅半醒/ 2022年02月19日 02:57/ 0 赞/ 201 阅读

相关 hdoj3709（数位dp）

题目链接：https://vjudge.net/problem/HDU-3709 题意：求出\[l,r\]中的平衡数，平衡数即存在一个中心点使得两边的力矩和相等。思路：首

桃扇骨/ 2021年12月21日 01:07/ 0 赞/ 256 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 260 阅读

相关数位DP模板

int a[20]; ll dp[20][state]; ll dfs(int pos,/state变量/,bool lead/前导零/,bool li

左手的ㄟ右手/ 2021年09月19日 05:42/ 0 赞/ 313 阅读