信奥赛C++提高组数位DP详解

一、基本概念

数位DP（Digit DP）是一种用于解决数字位相关计数问题的动态规划方法，常用于统计满足特定条件的数字个数。典型应用场景包括：

• 统计区间内包含不含某些数字的数的个数
• 统计满足特定位模式的数的数量
• 计算数字位属性的统计值（如数位和）

二、核心思想

1. 数位拆分：将数字转换为字符串或数组逐位处理
2. 状态压缩：记录前导零、是否受限、前位状态等关键信息
3. 记忆化搜索：通过DP数组缓存中间计算结果

三、状态设计要素

1. pos：当前处理的数位位置
2. limit：前面是否已经达到上限
3. pre：前一位数字的值
4. lead：前导零状态
5. 其他题目特定状态（如数位和、特定标记等）