数位dp模版

直接放一篇比较有代表性的数位dp学习的题目链接和标准的题解代码，由于题解代码较少就懒得解释更多了，关键就是从高位到低位的状态dfs➕记忆化➕对区间答案拆解为前缀差

https://www.luogu.com.cn/problem/P13085

#include <iostream> #include <vector> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; // dp[pos][pre] // pos: 当前处理到的位数 // pre: 上一位填写的数字 (0-9) // 因为 pre 有可能是前导零状态或者初始状态，我们在记忆化时通常只记录 lead=false 的情况 ll dp[20][15]; int a[20]; // 存储把数字拆解后的每一位 // dfs 函数 // pos: 当前位数 // pre: 上一位数字 // lead: 是否处于前导零状态 (true 表示前面全是 0) // limit: 最高位限制 (true 表示当前位受原数限制) ll dfs(int pos, int pre, bool lead, bool limit) { // 递归边界：填完了所有位，说明找到了一种合法方案，返回 1 if (pos == 0) return 1; // 记忆化搜索： // 如果没有最高位限制，且不是前导零状态，且该状态已经计算过，直接返回 if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre]; // 当前这一位能填的最大数字 // 如果受 limit 限制，只能填到 a[pos]；否则能填到 9 int up = limit ? a[pos] : 9; ll ans = 0; // 枚举当前位可能填的所有数字 i for (int i = 0; i <= up; i++) { // 判断当前填的 i 是否合法 // 情况 1: 之前全是前导零 if (lead) { if (i == 0) { // 如果当前继续填 0，则继续保持前导零状态，pre 不更新(或者传个特殊值，这里习惯用-2代表无前驱) // limit 更新：如果本来受限且当前填了上限(0==up)，则继续受限 ans += dfs(pos - 1, -2, true, limit && (i == up)); } else { // 如果当前填了非 0，前导零状态结束。 // 因为是第一位有效数字，不需要和上一位比较差值，直接合法 ans += dfs(pos - 1, i, false, limit && (i == up)); } } // 情况 2: 之前已经有有效数字了 else { // 必须满足题目条件：相邻数字之差 >= 2 if (abs(i - pre) >= 2) { ans += dfs(pos - 1, i, false, limit && (i == up)); } } } // 记录状态（仅在无限制且非前导零时记录，因为 limit 和 lead 特殊情况复用率低） if (!limit && !lead) dp[pos][pre] = ans; return ans; } // 计算 [1, x] 之间的 Windy 数 ll solve(ll x) { int len = 0; // 把数字 x 拆解存入数组，比如 123 -> a[3]=1, a[2]=2, a[1]=3 while (x) { a[++len] = x % 10; x /= 10; } // 记忆化数组初始化为 -1 // 注意：如果是多次询问，且 dp 状态与 limit/lead 无关，其实 dp 数组只需要 memset 一次。 // 但为了保险和逻辑简单，这里每次 solve 都清空（实际上这题 dp 数组可以复用，放在全局只初始化一次更优） // 本题数据量较小，每次初始化也没问题，若 TLE 可移到 main 函数外 memset(dp, -1, sizeof(dp)); // 从最高位 len 开始搜，pre 初始设为 -2（一个不可能干扰 0-9 判断的数） return dfs(len, -2, true, true); } int main() { ll a, b; cin >> a >> b; // 答案是 [1, b] 的数量 减去 [1, a-1] 的数量 cout << solve(b) - solve(a - 1) << endl; return 0; }