# 数位 DP（Digit DP）讲义

数位 DP 是一种用来解决**统计满足特定条件的数字个数**（通常在某个区间 $[L, R]$ 内）的算法。

它的核心思想是：**将数字按位拆开，利用高位对低位的限制关系，通过记忆化搜索或递推，计算出满足条件的数字方案数。**

---

## 一、 问题引入与核心模型

**典型问题：** 给定两个正整数 $L$ 和 $R$，求区间 $[L, R]$ 内有多少个数字满足某种性质（例如：不包含连续的数字 `49`、各位数字之和能被 $3$ 整除等）。

**数学转化：**
由于数位 DP 通常处理的是“从 $0$ 到 $N$”的前缀问题（记为 $\text{query}(N)$），因此区间 $[L, R]$ 的答案可以通过**前缀和思想**转化为：
$$\text{Ans} = \text{query}(R) - \text{query}(L - 1)$$

接下来，我们将重点讲解如何实现 $\text{query}(N)$。常用的实现方式有两种：**递归写法（记忆化搜索，强烈推荐）**和**递推写法（循环）**。

---

## 二、 写法一：递归写法（记忆化搜索）—— 强烈推荐

递归写法是数位 DP 中最主流、最不容易出错的写法。它的思路非常符合人类思考数字大小限制的过程。

### 1. 核心状态设计
通常递归函数 `dfs(pos, sum/status, limit, lead)` 包含以下几个核心参数：
*   `pos`：当前处理到从左往右的第几位（通常从高位 $len$ 降到 $1$，或者从 $0$ 到 $len-1$）。
*   `limit`：布尔值，表示**当前是否受到了 $N$ 的限制**。
    *   如果 `limit = true`，说明前面填的数字和 $N$ 的前缀完全相同，当前这一位不能随便填，最大只能填 $N$ 的当前位数字 $limit\_val$。
    *   如果 `limit = false`，说明前面已经填了比 $N$ 小的数字，当前这一位可以从 $0$ 自由地填到 $9$。
*   `lead`：布尔值，表示**当前是否有着前导零（Leading Zeros）**。
    *   如果 `lead = true`，说明前面填的都是 $0$（或者还没开始填）。这在处理“不能有前导零”或“统计特定数字出现次数（前导零不计）”时非常关键。
*   其他状态参数：根据题目要求而定，比如 `sum`（当前各位数字和）、`pre`（上一位填的数字）等。

### 2. 记忆化剪枝（Memoization）
*   **什么时候能记忆化？** 只有当 `limit = false` 且 `lead = false` 时，当前状态的结果才可以被缓存（Memorization）。
*   **为什么？** 因为如果 `limit = true`，说明当前的搜索受制于 $N$，这个状态具有唯一性，不能复用；同理，有前导零时的状态和无前导零时的状态性质不同。

### 3. 模板代码框架（C++）

```cpp
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int dp[20][state_size]; // 记忆化数组，大小视题目状态而定
int digits[20];         // 存储 N 的每一位

// dfs 函数：根据题目具体要求设计参数
int dfs(int pos, int state, bool limit, bool lead) {
    // 1. 递归边界：如果 pos 已经处理完（比如从 len-1 降到 0，或者从 0 到 len）
    if (pos == 0) { 
        return 1; // 找到了一个合法数字
    }

// 2. 记忆化：在不受限制且没有前导零的情况下，直接返回缓存结果
    if (!limit && !lead && dp[pos][state] != -1) {
        return dp[pos][state];
    }

int res = 0;
    // 3. 确定当前位可以填的最大数字
    int up = limit ? digits[pos] : 9;

// 4. 枚举当前位可以填的数字 i
    for (int i = 0; i <= up; ++i) {
        // ---- 剪枝与特殊处理 ----
        // 比如：如果不能有前导零，且当前填 0，则 lead 保持 true
        // bool next_lead = lead && (i == 0); 
        // 比如：如果题目要求不连续出现 49，可以在这里判断合法性
        // if (pre == 4 & i == 9) continue;

// 5. 递归下一位
        // 只有当“原本受限制(limit为true)”且“当前填到了最大值(i == up)”时，下一位才继续受限制
        res += dfs(pos - 1, next_state, limit && (i == up), next_lead);
    }

// 6. 记忆化并返回
    if (!limit && !lead) {
        dp[pos][state] = res;
    }
    return res;
}

int solve(long long n) {
    if (n < 0) return 0;
    int len = 0;
    while (n) {
        digits[++len] = n % 10;
        n /= 10;
    }
    memset(dp, -1, sizeof(dp)); // 每次查询前初始化记忆化数组
    return dfs(len, initial_state, true, true);
}

int main() {
    long long L, R;
    cin >> L >> R;
    cout << solve(R) - solve(L - 1) << endl;
    return 0;
}
```

---

## 三、 写法二：递推写法（数位 DP 的循环实现）

递推写法从低位到高位（或高位到低位），利用状态转移方程直接计算。它的好处是**运行速度快、没有递归开销**，但代码逻辑较递归更为绕脑，尤其在处理上下界限制时。

### 1. 核心思想
我们将 $N$ 转化为字符串或数字数组。
*   `dp[i][state]` 表示：处理到从低到高第 $i$ 位时，状态为 `state` 的方案数。
*   在递推时，我们通常先预处理出“不受任何限制”时的通用 DP 表（类似于数位组合数学）。
*   然后通过一个循环，从高位到低位扫描 $N$ 的每一位，累加“当前位选比 $N$ 小的数”时后面所有自由选择的方案数，同时维护前缀状态。

### 2. 递推写法的一般步骤（以统计长度和数位特征为例）

通常递推法分为两步：
1. **预处理（Precompute）**：计算没有上限限制时，各长度、各状态的方案数。
2. **逐位统计（Count）**：对照数字 $N$ 的每一位，分情况累加答案。

由于递推写法对每种题目的边界处理（如前导零、数位约束）差异较大，且容易写出复杂的分类讨论，**在竞赛和面试中，绝大多数人更倾向于选择逻辑清晰的“递归写法（记忆化搜索）”**。

> **注：** 如果必须要用递推，建议也可以采用“把 $N$ 转成 $base$ 进制或转换为长度固定的字符串，高位补零”，利用类似自动机的思想进行状态转移。但若非特殊性能要求（如极大规模的连续多组询问），**优先推荐递归写法**。

---

## 四、 实战演习：以“不含 49 的数字”为例

**题目：** 求区间 $[1, n]$ 中不包含连续数字 `49` 的正整数个数。($1 \le n \le 2^{31}-1$)

### 递归写法实现：
状态设计：
*   `pos`：当前位。
*   `pre`：前一位数字是什么（用于判断是否构成了 `4’‘9’`）。
*   `limit`：是否有上限约束。
*   `lead`：是否有前导零。

```cpp
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int dp[20][10];
int digits[20];

int dfs(int pos, int pre, bool limit, bool lead) {
    if (pos == 0) return 1; // 搜索到底，说明找到了一个合法数字

// 记忆化（注意：有前导零或受限时不能直接返回）
    if (!limit && !lead && dp[pos][pre] != -1) {
        return dp[pos][pre];
    }

int up = limit ? digits[pos] : 9;
    int res = 0;

for (int i = 0; i <= up; ++i) {
        // 剪枝：如果前一位是 4，这一位是 9，则不合法，跳过
        if (pre == 4 && i == 9) continue;

// 处理前导零：如果当前是最高位且填了 0，则下一位依然算作有前导零
        // 有前导零时，pre 可以设为一个无效值（比如 -1），这样就不会触发 pre==4 && i==9 的误判
        int next_pre = (lead && i == 0) ? -1 : i;

res += dfs(pos - 1, next_pre, limit && (i == up), lead && (i == 0));
    }

if (!limit && !lead) {
        dp[pos][pre] = res;
    }
    return res;
}

long long solve(long long n) {
    if (n < 0) return 0;
    int len = 0;
    while (n) {
        digits[++len] = n % 10;
        n /= 10;
    }
    memset(dp, -1, sizeof(dp));
    // 初始时 pre 设为 -1，lead 设为 true
    return dfs(len, -1, true, true);
}

int main() {
    long long n;
    while (cin >> n) {
        cout << solve(n) << endl;
    }
    return 0;
}
```

---

## 五、 总结与排错指南

1. **多组数据清空**：由于每次查询的 $N$ 不同，或者记忆化数组需要重置，切记在每次 `solve()` 时用 `memset(dp, -1, sizeof(dp))` 清空。如果状态维度较小，也可以直接在全局初始化。
2. **前导零的影响**：
   * 前导零往往会干扰某些状态（例如：求不包含数字 `4` 的数，前导零如果算作数字 `0` 是合法的，但如果题目要求统计数字出现的总次数，前导零不能算进去）。
   * 一定要在递归时明确 `lead` 变量的作用。
3. **为什么递归更好？** 递归写法（记忆化搜索）本质上是在状态空间树上进行 DFS，它不需要我们费心去推导复杂的边界状态转移方程，只需要关心“当前这一步能填什么，填完之后对下一步有什么影响”即可。

数位 DP（Digit DP）讲义

数位 DP 是一种用来解决统计满足特定条件的数字个数（通常在某个区间 $[L, R]$ 内）的算法。

它的核心思想是：将数字按位拆开，利用高位对低位的限制关系，通过记忆化搜索或递推，计算出满足条件的数字方案数。

一、问题引入与核心模型

典型问题： 给定两个正整数 $L$ 和 $R$，求区间 $[L, R]$ 内有多少个数字满足某种性质（例如：不包含连续的数字 49、各位数字之和能被 $3$ 整除等）。

数学转化： 由于数位 DP 通常处理的是“从 $0$ 到 $N$”的前缀问题（记为 $\text{query}(N)$），因此区间 $[L, R]$ 的答案可以通过前缀和思想转化为： $$\text{Ans} = \text{query}(R) - \text{query}(L - 1)$$

接下来，我们将重点讲解如何实现 $\text{query}(N)$。常用的实现方式有两种：递归写法（记忆化搜索，强烈推荐）和递推写法（循环）。

二、写法一：递归写法（记忆化搜索）—— 强烈推荐

递归写法是数位 DP 中最主流、最不容易出错的写法。它的思路非常符合人类思考数字大小限制的过程。

1. 核心状态设计

通常递归函数 dfs(pos, sum/status, limit, lead) 包含以下几个核心参数： * pos：当前处理到从左往右的第几位（通常从高位 $len$ 降到 $1$，或者从 $0$ 到 $len-1$）。 * limit：布尔值，表示当前是否受到了 $N$ 的限制。 * 如果 limit = true，说明前面填的数字和 $N$ 的前缀完全相同，当前这一位不能随便填，最大只能填 $N$ 的当前位数字 $limit_val$。 * 如果 limit = false，说明前面已经填了比 $N$ 小的数字，当前这一位可以从 $0$ 自由地填到 $9$。 * lead：布尔值，表示当前是否有着前导零（Leading Zeros）。 * 如果 lead = true，说明前面填的都是 $0$（或者还没开始填）。这在处理“不能有前导零”或“统计特定数字出现次数（前导零不计）”时非常关键。 * 其他状态参数：根据题目要求而定，比如 sum（当前各位数字和）、pre（上一位填的数字）等。

2. 记忆化剪枝（Memoization）

什么时候能记忆化？ 只有当 limit = false 且 lead = false 时，当前状态的结果才可以被缓存（Memorization）。
为什么？ 因为如果 limit = true，说明当前的搜索受制于 $N$，这个状态具有唯一性，不能复用；同理，有前导零时的状态和无前导零时的状态性质不同。

3. 模板代码框架（C++）

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int dp[20][state_size]; // 记忆化数组，大小视题目状态而定
int digits[20];         // 存储 N 的每一位

// dfs 函数：根据题目具体要求设计参数
int dfs(int pos, int state, bool limit, bool lead) {
    // 1. 递归边界：如果 pos 已经处理完（比如从 len-1 降到 0，或者从 0 到 len）
    if (pos == 0) { 
        return 1; // 找到了一个合法数字
    }

    // 2. 记忆化：在不受限制且没有前导零的情况下，直接返回缓存结果
    if (!limit && !lead && dp[pos][state] != -1) {
        return dp[pos][state];
    }

    int res = 0;
    // 3. 确定当前位可以填的最大数字
    int up = limit ? digits[pos] : 9;

    // 4. 枚举当前位可以填的数字 i
    for (int i = 0; i <= up; ++i) {
        // ---- 剪枝与特殊处理 ----
        // 比如：如果不能有前导零，且当前填 0，则 lead 保持 true
        // bool next_lead = lead && (i == 0); 
        // 比如：如果题目要求不连续出现 49，可以在这里判断合法性
        // if (pre == 4 & i == 9) continue; 

        // 5. 递归下一位
        // 只有当“原本受限制(limit为true)”且“当前填到了最大值(i == up)”时，下一位才继续受限制
        res += dfs(pos - 1, next_state, limit && (i == up), next_lead);
    }

    // 6. 记忆化并返回
    if (!limit && !lead) {
        dp[pos][state] = res;
    }
    return res;
}

int solve(long long n) {
    if (n < 0) return 0;
    int len = 0;
    while (n) {
        digits[++len] = n % 10;
        n /= 10;
    }
    memset(dp, -1, sizeof(dp)); // 每次查询前初始化记忆化数组
    return dfs(len, initial_state, true, true);
}

int main() {
    long long L, R;
    cin >> L >> R;
    cout << solve(R) - solve(L - 1) << endl;
    return 0;
}

三、写法二：递推写法（数位 DP 的循环实现）

递推写法从低位到高位（或高位到低位），利用状态转移方程直接计算。它的好处是运行速度快、没有递归开销，但代码逻辑较递归更为绕脑，尤其在处理上下界限制时。

1. 核心思想

我们将 $N$ 转化为字符串或数字数组。 * dp[i][state] 表示：处理到从低到高第 $i$ 位时，状态为 state 的方案数。 * 在递推时，我们通常先预处理出“不受任何限制”时的通用 DP 表（类似于数位组合数学）。 * 然后通过一个循环，从高位到低位扫描 $N$ 的每一位，累加“当前位选比 $N$ 小的数”时后面所有自由选择的方案数，同时维护前缀状态。

2. 递推写法的一般步骤（以统计长度和数位特征为例）

通常递推法分为两步： 1. 预处理（Precompute）：计算没有上限限制时，各长度、各状态的方案数。 2. 逐位统计（Count）：对照数字 $N$ 的每一位，分情况累加答案。

由于递推写法对每种题目的边界处理（如前导零、数位约束）差异较大，且容易写出复杂的分类讨论，在竞赛和面试中，绝大多数人更倾向于选择逻辑清晰的“递归写法（记忆化搜索）”。

注：如果必须要用递推，建议也可以采用“把 $N$ 转成 $base$ 进制或转换为长度固定的字符串，高位补零”，利用类似自动机的思想进行状态转移。但若非特殊性能要求（如极大规模的连续多组询问），优先推荐递归写法。

四、实战演习：以“不含 49 的数字”为例

题目： 求区间 $[1, n]$ 中不包含连续数字 49 的正整数个数。($1 \le n \le 2^{31}-1$)

递归写法实现：

状态设计： * pos：当前位。 * pre：前一位数字是什么（用于判断是否构成了 4’‘9’）。 * limit：是否有上限约束。 * lead：是否有前导零。

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int dp[20][10];
int digits[20];

int dfs(int pos, int pre, bool limit, bool lead) {
    if (pos == 0) return 1; // 搜索到底，说明找到了一个合法数字

    // 记忆化（注意：有前导零或受限时不能直接返回）
    if (!limit && !lead && dp[pos][pre] != -1) {
        return dp[pos][pre];
    }

    int up = limit ? digits[pos] : 9;
    int res = 0;

    for (int i = 0; i <= up; ++i) {
        // 剪枝：如果前一位是 4，这一位是 9，则不合法，跳过
        if (pre == 4 && i == 9) continue;

        // 处理前导零：如果当前是最高位且填了 0，则下一位依然算作有前导零
        // 有前导零时，pre 可以设为一个无效值（比如 -1），这样就不会触发 pre==4 && i==9 的误判
        int next_pre = (lead && i == 0) ? -1 : i;

        res += dfs(pos - 1, next_pre, limit && (i == up), lead && (i == 0));
    }

    if (!limit && !lead) {
        dp[pos][pre] = res;
    }
    return res;
}

long long solve(long long n) {
    if (n < 0) return 0;
    int len = 0;
    while (n) {
        digits[++len] = n % 10;
        n /= 10;
    }
    memset(dp, -1, sizeof(dp));
    // 初始时 pre 设为 -1，lead 设为 true
    return dfs(len, -1, true, true);
}

int main() {
    long long n;
    while (cin >> n) {
        cout << solve(n) << endl;
    }
    return 0;
}

五、总结与排错指南

多组数据清空：由于每次查询的 $N$ 不同，或者记忆化数组需要重置，切记在每次 solve() 时用 memset(dp, -1, sizeof(dp)) 清空。如果状态维度较小，也可以直接在全局初始化。
前导零的影响：
前导零往往会干扰某些状态（例如：求不包含数字 4 的数，前导零如果算作数字 0 是合法的，但如果题目要求统计数字出现的总次数，前导零不能算进去）。
一定要在递归时明确 lead 变量的作用。
为什么递归更好？ 递归写法（记忆化搜索）本质上是在状态空间树上进行 DFS，它不需要我们费心去推导复杂的边界状态转移方程，只需要关心“当前这一步能填什么，填完之后对下一步有什么影响”即可。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com