type
status
date
slug
summary
tags
category
icon
password
Property
Mar 4, 2023 02:37 AM
其实早在几个月前打周赛的时候就碰到过数位dp的题，当时看题解都看不懂，然后去OI wiki上看依旧看不懂，于是我在acwing上打卡碰到这题直接摆烂了三天，今天好好总结一下，啃下这块硬骨头。 😫
今天只讨论最简单的数位DP题目：
给定两个正整数 a，b，求在 [a，b] 中的所有整数中，每个数码（digit）各出现了多少次
数位 DP 的基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即
那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。
实例分析
抽象化例子
实现
小结
- 这道题搞清楚只能算我有了对数位DP这类题目最基本的求解能力，后边的路还很长。。
参考
- 作者:GJJ
- 链接:https://blog.gaojj.cn/article/blog-17
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。