期望dp数位dp

### 数位 DP 算法详解 数位 DP 是一种基于动态规划的思想来解决特定计数问题的方法。它通过将数字分解成各个数位（如个位、十位等），并利用记忆化搜索的方式快速统计某个范围内满足某些条件的数字的数量。 #### 基本概念 数位 DP 主要用于解决如下形式的问题：给定一个闭区间 $[L, R]$，求该区间内满足某种条件的整数数量[^1]。为了高效解决问题，通常会采用 **记忆化搜索** 或者 **状态转移方程** 来减少重复计算的时间复杂度。 --- #### 核心思想 数位 DP 的核心在于将其转化为对每一位上的数值进行处理，并记录中间结果以便后续重用。以下是其主要特点： - 将数字按位拆分，逐位分析。 - 使用 DFS 配合记忆化数组存储子问题的结果。 - 利用前缀性质优化时间复杂度。 具体来说，在实现过程中需要考虑以下几个维度的状态变量： 1. 当前正在处理哪一位（`pos`）； 2. 是否受到上界约束（即当前数字是否等于上限 `R` 的对应位置值，记作 `limit`）； 3. 是否受下界约束（同理可定义为 `lower_limit`，但在实际应用中较少涉及）； 4. 已经构建的部分是否满足题目中的特殊条件（比如不包含连续两位相同的情况或其他限制条件）。 这些状态共同构成了递归函数的核心参数列表[^2]。 --- #### 实现方法 下面是一个通用的数位 DP 模板： ```cpp #include <bits/stdc++.h> using namespace std; // 定义全局变量 int dp[20][state_size]; // 记忆化数组 vector<int> num; // 存储目标数字的各位表示 // dfs 函数原型 long long dfs(int pos, int state, bool limit); // 初始化入口函数 long long solve(long long x) { num.clear(); while (x > 0) { // 将数字转为逆序存储的形式 num.push_back(x % 10); x /= 10; } reverse(num.begin(), num.end()); memset(dp, -1, sizeof(dp)); // 清空记忆化缓存 return dfs(0, initial_state, true); // 开始递归调用 } // 具体的dfs逻辑 long long dfs(int pos, int state, bool limit) { if (pos == num.size()) return check(state); // 边界情况判断 if (!limit && dp[pos][state] != -1) return dp[pos][state]; int up = limit ? num[pos] : 9; // 如果有限制，则取较小值作为上限；否则可以达到最大可能值9 long long res = 0; for (int i = 0; i <= up; ++i) { int new_state = update(state, i); // 更新状态机 if (valid(new_state)) { // 只有合法的新状态才继续向下扩展 res += dfs(pos + 1, new_state, limit && (i == up)); } } if (!limit) dp[pos][state] = res; // 缓存无限制下的结果 return res; } ``` 上述代码展示了如何设计一个基础框架来进行数位 DP 的操作。其中需要注意的关键点包括但不限于以下几点： - 如何初始化输入数据以及转换为目标格式； - 设计合适的状态空间大小 (`state_size`) 和初始状态 (`initial_state`); - 明确哪些条件下允许进入下一步迭代(`check`, `update`, and `valid`); --- #### 应用实例 以 HDU-2089 “不要62”为例说明其实现过程。此题要求找出 `[l, r]` 范围内的所有不含字符串 `"62"` 的正整数总数。 ##### 解决方案 我们可以先分别算出从零到右端点 `r` 中符合条件的数目再减去同样规则作用于左端点左边区域所得值即可得出最终答案。 ```cpp bool valid(string s){ string t="62"; if(s.find(t)!=string::npos)return false; return true; } ``` 这里省略了完整的程序清单但由于遵循之前提到的标准模式所以应该很容易理解整个流程是如何运作起来的[^3]。 --- ### 总结 通过对数位 DP 技巧的学习可以看出这是一种非常有效的手段用来应对那些单纯依靠暴力穷举无法胜任的大规模查询请求场景。只要掌握了基本原理加上灵活运用就能轻松搞定许多看似复杂的难题啦！