浅谈数位 DP

zhangjinxuan · 发表于 2024-12-7 10:34:58

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 zhangjinxuan 于 2025-1-21 18:39 编辑

浅谈数位 DP

Update Logs:
- [2024/11/26 23:00] 完成了未完成的部分。

更好的阅读体验。

本文章的作者与上处链接所指向的文章的作者是同一个人。

前言

本文全方面讲解了数位 DP 从基础的计数到入土的拓展（例如自动机、进退位和偏序），我认为我至少比 OI-wiki 写得好，但总有缺漏或错误之处，欢迎大佬指出。

这里我专门整理了一个数位 DP 专题的题单，欢迎收藏。

声明：请勿搬运。

引言

此处部分参考于 OI-wiki。

数位 DP 的题目一般是如下情形：

- 在一个区间范围内统计一些东西。

在区间范围很小的时候，显然可以暴力枚举，但是当区间范围很大的时候，就要使用数位 DP 优化。

为什么数位 DP 就能优化这一点呢？数位 DP 的核心思想大概就是，对于很多个数字，他们都有可能存在相同的贡献，比如在 P2602（分别统计一个范围内所有数位的出现次数）一题中，数字 $12345$ 和数字 $54321$，$3$ 都在百位出现了 $2$ 次，如果统计的区间范围足够大，那么这个数字会更多，所以我们就可以使用计数的方法优化。

而 DP 是什么呢？比方说一道题目要统计 $1\sim n$ 的所有数字的数位和的和，会发现 $123456$ 和 $123457$ 这两个数字他们都有一个共同的前缀，这种前缀只有在暴力枚举的时候会增加复杂度，而 DP 就不会存在这一点。

因而，数位 DP 大概也就有两种分类，并且细分为多种写法：

- 数位计数。
- 纯数位计数。
- 拆分区间范围。
- 数位 DP。
- 纯 DP
- 枚举 LCP + DP。

更复杂的情况会在对应的位置讲解，不过不管怎样，都需要考察选手对于数位的深刻理解能力。

下文会介绍所有常用的数位 DP 写法，并且介绍部分简单的拓展。

希望您能在阅读下文之前评分和收藏，谢谢！

登录/注册后可看大图

zhangjinxuan · 发表于 2024-12-7 10:48:45

本帖最后由 zhangjinxuan 于 2024-12-9 21:08 编辑

纯胡说，没什么东西

jjwteam · 发表于 2025-4-24 15:55:00

学习一下

zxb_zxb · 发表于 2025-4-23 22:06:44

新人学习

zhangjinxuan · 发表于 2025-4-23 22:06:01

小鱼新手 · 发表于 2025-3-21 14:08:39

还看不懂，努力学习中

小鱼新手 · 发表于 2025-3-21 14:07:55

zhangjinxuan · 发表于 2025-2-9 11:48:03

sjmr6716 · 发表于 2025-1-29 01:21:52

学习学习

zhangjinxuan · 发表于 2025-1-27 11:01:05

zhangjinxuan · 发表于 2025-1-21 17:59:55

changeliu · 发表于 2025-1-14 10:22:13

学习,学习一下

zhangjinxuan · 发表于 2025-1-12 22:15:13

zsy0226 · 发表于 2025-1-4 14:30:37

失踪人口回归

尹玄睿 · 发表于 2024-12-25 09:55:11

点个赞！！！

尹玄睿 · 发表于 2024-12-25 09:54:27

紫藤竹轩 · 发表于 2024-12-24 10:55:29

点去怎么没反应的呢

紫藤竹轩 · 发表于 2024-12-24 10:54:52

没看明白

liujun_fishc · 发表于 2024-12-22 05:33:36

zyx2012 · 发表于 2024-12-21 08:07:04

谢谢

Mike_python小 · 发表于 2024-12-20 21:12:45

看看

账号		自动登录	找回密码
密码			立即注册

[学习笔记] 浅谈数位 DP

马上注册，结交更多好友，享用更多功能^_^

评分

回帖奖励 +2 鱼币

回帖奖励 +2 鱼币

回帖奖励 +2 鱼币

回帖奖励 +2 鱼币

回帖奖励 +2 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币