刷算法题的人看到“问题 N等差数”这种命名应该都会会心一笑。这就是OJ平台上最常见的一类题名一个编号、一个冒号、一个核心概念干净利落。题目本身的定义很简单——把一个整数按十进制拆成各位数字如果相邻数位之间的差值恒定不变这个数就叫等差数。1234是因为1、2、3、4之间差值都是113579也是差值固定为2但121不是它的差分序列是1和-1别把它跟回文数混在一起。这类题的价值不在“定义”本身而在它延伸出来的各种考法单个数的判断、区间内等差数的计数、第K个等差数的查询一个比一个考基本功。我这次就把“等差数”这一类问题从头到尾拆开讲适合正在打算法基础的同学、准备竞赛的选手以及想拿这种小题练手代码能力的开发者。1. 题目拆解等差数到底考什么1.1 一位数、两位数、0、负数怎么算虽然“等差数”这个名字看着直观但一到边界条件就会出现分歧。以十进制表示来说设一个正整数从高位到低位的数位是 a1, a2, ..., ak等差数的定义是对任意 i 属于 [2, k-1]都有 a[i1] - a[i] 等于 a[i] - a[i-1]这个恒定差值就叫公差。公差可以是负数比如 987 的公差是 -1可以是0比如 555也可以是正数比如 1234 的公差是 1、369 的公差是 3。边界情况里一位数只有一个数位不存在相邻差但按竞赛惯例它天然满足等差条件所以 5、7、9 都算等差数。两位数只有一对相邻差无论这对差是多少都满足定义所以 10 到 99 全部都是等差数。这一点很多人在手算验证时会忽略误以为只有 11、22、33 这种才算实际上 17、28、39 也是等差数因为判断条件只要求“差值恒定”并不要求差值非零。0 这个数字要看题目范围如果题目说的是正整数0 不属于讨论范围如果题目在非负整数域内提问那么 0 可以按“一位数”处理算作等差数。负数一般不用考虑因为负号不是十进制数位少数题目如果输入出现负数我的做法是先判断符号位再对绝对值拆位。总而言之写代码前最好把题目里“数”的范围确认清楚不然后面处理边界时会有一堆麻烦。1.2 两档考法判断单个数与统计区间个数“问题 N等差数”在OJ里常见的问法分两档。第一档是给一个整数 x判断它是不是等差数。这个很简单把 x 拆成数位后从头到尾扫一遍O(log10(x)) 的复杂度就搞定long long 范围内最多 19 位实际上就是一个循环的事。第二档才是真正意义上的算法题给定区间 [L, R]统计区间内一共有多少个等差数。第二档的问法看着也就比第一档多了一个“区间”但难度完全不一样。当 R 只有 10^6 时暴力枚举勉强可过当 R 上到 10^12 甚至 10^18暴力就彻底没戏了必须用数位DP。很多课程设计、算法作业把这道题当压轴就是因为第二档能同时考察拆位、动态规划状态设计、前导零处理和边界控制这几项硬功夫。而且它不像一些纯背模板的数位DP题那样无脑公差这个东西需要自己设计状态和转移有一定区分度。2. 我建议你先暴力能跑通比什么都强2.1 一位一位拆一位一位校验遇到这种题我的习惯永远是先写一个暴力版本把“到底怎么判断一个数是不是等差数”这件事彻底想清楚。判断函数的核心逻辑不复杂拆位、算差值、往后对比。bool isArithmetic(long long x) { if (x 0) return false; if (x 9) return true; // 一位数按等差数处理 vectorint digits; while (x 0) { digits.push_back(x % 10); x / 10; } reverse(digits.begin(), digits.end()); if (digits.size() 2) return true; // 两位数一定是等差数 int d digits[1] - digits[0]; for (int i 2; i (int)digits.size(); i) { if (digits[i] - digits[i - 1] ! d) return false; } return true; }有几个细节值得说。先单独处理 x 9这样 0 到 9 这些一位数不用进 while 循环拆位避免后面处理空数组。拆位之后先 reverse因为 while 循环每次取最低位得到的数组是低位到高位而判断等差需要从高位往低位看。前两位的差值 d 可以先算出来后面的每一位只要和 d 不一样就直接返回 false不需要把所有差值都存下来再统一判断那样徒增一次遍历还容易写错。基于这个判断函数统计区间的暴力主程序非常简单int countByBruteForce(long long L, long long R) { int ans 0; for (long long x L; x R; x) { if (isArithmetic(x)) ans; } return ans; }这段代码没什么可优化的它的价值在于“正确性非常直观”。当你后面写数位DP时这个暴力版就是你做对拍、验证错误的最佳工具。我在实际做题时经常先用暴力跑小范围数据把几个关键区间的答案记下来作为后续DP输出的参照。2.2 暴力的复杂度瓶颈在哪里暴力解法的时间复杂度是 O((R - L 1) * log10(R))其中 log10(R) 来自拆位循环。在 long long 范围内最多 19 位数所以每个数字大约做 19 次取余和除法。当区间长度为 10^6 时总操作量大约是 2 * 10^7 次C 能在一秒左右跑完区间长度到 10^7 以上就比较危险了如果还叠加上 reverse 和 vector 分配超时概率很高。Python 的常数更大10^5 基本是极限再往上就很难受。所以暴力版本的适用场景很清晰一是题目数据范围小比如 R 10^6可以直接交暴力拿分二是作为对拍程序使用拿来验证DP解法在随机小数据下是否正确。我在下面的章节里会不断回到这个暴力版因为它是我写DP时最重要的“参考答案”。3. 高效解法数位DP统计区间等差数3.1 把“从高位往低位读”这件事建模成状态机数位DP的第一道坎是状态设计。初学者最容易犯的错是想把整个数字串存进状态里这显然不行。正确做法是考虑我们“从左往右读数字”的过程中到底需要保留哪些信息才能判断等差。从左往右读时判断一个数是否为等差数本质上是在维护三个信息当前读到第几位、上一位数字是什么、当前累积的“差分结果”是否保持一致。因此DP状态可以设计为四维pos当前处理的数位下标从0开始pre上一位数字取值范围 0 到 9diff当前公差范围 -9 到 9started是否已经开始处理有效数字0 表示还在前导零阶段1 表示已经从第一个非零数位开始了。这里有一个非常关键的点就是前导零。数字 12 写成数位其实是 1 和 2但在拆位过程中为了对齐长度你会自然而然地想到高位有若干个 0。如果把这些前导零也读进来12 就会变成 0、0、1、2差分序列是 0、1、1显然会被误判为非等差数。started 这个布尔状态就是用来剔除前导零干扰的在遇到第一个非零数位之前我们不记录 pre 也不记录 diff。还有一个小状态叫“公差是否已经确定”。当一个数只有一位有效数字时比如我们刚读到第一个数位“1”还没看到第二位这时候公差根本不存在。所以 diff 需要有一个特殊取值表示“未定”我用 19 表示未定。真实公差 -9 到 9 映射到 0 到 18所以 diff 这个维度大小开 20。pre 在未开始阶段也没有意义我用 10 作为占位值所以 pre 维度开 11。最终 dp 数组大概是 dp[20][11][20][2]状态量非常小。3.2 公差为什么要加9数组下标不能是负数很多写法会直接用真实公差 -9 到 9 来当数组下标这在 C 里是会越界的。我的习惯是把所有公差存成“真实公差 9”这样 -9 到 9 映射成 0 到 18既不会越界又方便还原。比如公差 d -1存储值就是 8d 0存储值就是 9d 3存储值就是 12。状态转移的时候从高位往低位枚举当前位 d上限由 tight 决定如果之前所有位都贴着上界那么当前位最大只能是上界的那一位否则可以填到 9。接下来分四种情况尚未开始且当前位为 0继续保持未开始状态pre 和 diff 都用占位值started 保持 0尚未开始且当前位非 0有效数字从这一位开始started 置 1pre 更新为当前位diff 设为 19未定已开始且 diff 为 19说明目前只有一位有效数字填入的数字是第二位此时才真正确定公差把当前位减去 pre 得到真实公差加 9 存进 diff已开始且 diff 已确定要求当前位与 pre 的差值必须等于存储公差减去 9如果不等直接剪枝如果相等更新 pre 为当前位diff 不变。最后递归到 pos len 时如果 started 为 1说明这是一个有效数字且全程满足等差条件返回 1如果 started 还是 0说明整个数字就是 0按前文的约定返回 0若题目把 0 算等差数这里改为返回 1。这个简单的判断就是整个数位DP的出口。3.3 C完整实现与三组验证数据我直接贴一份经过对拍的完整C代码核心就是上面的 dfs 递归。#include bits/stdc.h using namespace std; using int64 long long; int64 dp[20][11][20][2]; vectorint digit; int64 dfs(int pos, int pre, int diff, int started, int tight) { if (pos (int)digit.size()) { return started ? 1 : 0; } if (!tight dp[pos][pre][diff][started] ! -1) { return dp[pos][pre][diff][started]; } int limit tight ? digit[pos] : 9; int64 ans 0; for (int d 0; d limit; d) { int npre pre, ndiff diff, nstarted started; if (!started) { if (d ! 0) { nstarted 1; npre d; ndiff 19; } } else if (diff 19) { ndiff d - pre 9; npre d; } else { if (d - pre ! diff - 9) continue; npre d; } ans dfs(pos 1, npre, ndiff, nstarted, tight d limit); } if (!tight) dp[pos][pre][diff][started] ans; return ans; } int64 countArithmetic(int64 x) { if (x 0) return 0; digit.clear(); while (x 0) { digit.push_back(x % 10); x / 10; } reverse(digit.begin(), digit.end()); memset(dp, -1, sizeof(dp)); return dfs(0, 10, 19, 0, 1); } int main() { int64 L, R; cin L R; cout countArithmetic(R) - countArithmetic(L - 1) \n; return 0; }这份代码我本地跑了几组数据都和暴力版对上了。比如 [1, 100] 的答案是 99因为 1 到 99 全是等差数而 100 不是[1, 1000] 的答案是 144由 1 到 99 的 99 个、100 到 999 的三位等差数 45 个组成[1, 10000] 的答案是 174也就是 99 45 30其中 30 是 1000 到 9999 的四位等差数个数。这三组数据我建议你拿到代码后第一时间验证能对上基本说明状态转移没问题。如果要在 Python 里写核心部分完全一样只是用 lru_cache 做记忆化会更方便。需要注意这里我把 tight 参数也放了进去虽然会多缓存一些状态但状态总量小影响不大。实际比赛中用 C 的数组记忆化会更可控。from functools import lru_cache def count_upper(x): if x 0: return 0 digits list(map(int, str(x))) if x 0 else [] lru_cache(None) def dfs(pos, pre, diff, started, tight): if pos len(digits): return 1 if started else 0 limit digits[pos] if tight else 9 ans 0 for d in range(limit 1): np, nd, ns pre, diff, started if not started: if d ! 0: ns, np, nd 1, d, 19 elif diff 19: nd, np d - pre 9, d else: if d - pre ! diff - 9: continue np d ans dfs(pos 1, np, nd, ns, tight and d limit) return ans return dfs(0, 10, 19, 0, True) def count_interval(L, R): return count_upper(R) - count_upper(L - 1)4. 常见问题与调试实录4.1 前导零最隐蔽的坑前导零问题我在前面反复强调因为它就是做数位DP最容易翻车的地方。我第一次写这题时没有加 started 状态结果统计 [1, 100] 输出 90少算了 1 到 9 那 9 个一位数。为什么因为拆分 001、002 这些数字时前导零被当成真实数位读进去1 被读成 0、0、1差分序列是 0 和 1不满足等差条件于是被错误地排除了。加了 started 之后前导零阶段会一直“空转”直到遇到非零数字才开始记录 pre 和 diff。这个状态不仅适用于等差数所有需要“按数字真实位判断”的数位DP题基本都用得到比如统计不含某个数字的个数时也要避免前导零的影响。如果发现统计结果偏小第一反应就应该是前导零处理问题。4.2 边界值0、负数与long long极限边界值的处理看似简单实际写起来很容易炸。首先是 L - 1如果 L 是 0那么 countArithmetic(L - 1) 会变成 countArithmetic(-1)必须在函数入口判断 x 0 时返回 0否则后面 while 循环对负数取余会有奇怪行为。其次是 0 本身本实现的约定是“正整数范围0 不算等差数”所以在 dfs 出口处 started 为 0 时返回 0如果题目明确把 0 算作一位等差数这里要改成 1并且 countArithmetic(0) 应该对应 1。另一个边界是 long long 的极限。long long 最大能表示 19 位数所以 dp 第一维开 20 就够了。但如果题目用 unsigned long long 或者高精度大整数位数会到 20 甚至更多dp 数组大小必须跟着调。我习惯在写题前先算清楚最大位数避免数组开小导致越界。还有一点记忆化只在 !tight 时写入这是数位DP的常识但很多人会顺手把 tight 也写进 dp 维度导致状态冗余甚至出错注意区分。4.3 暴力与DP的交叉验证方法数位DP写完不验证很容易留下隐形 bug。我最推荐的做法是写一个小型对拍程序把所有小范围区间全部跑一遍。代码不复杂就是把暴力答案和DP答案逐一对比发现不同立刻打印。int main() { for (int L 0; L 200; L) { for (int R L; R 200; R) { int ans1 countByBruteForce(L, R); int64 ans2 countArithmetic(R) - countArithmetic(L - 1); if (ans1 ! ans2) { printf(mismatch L%d R%d brute%d dp%lld\n, L, R, ans1, ans2); return 0; } } } puts(all ok); return 0; }这个对拍程序把 0 到 200 的所有区间组合都验证一遍虽然范围不大但能覆盖一位数、两位数、三位数的所有边界足以暴露大部分状态转移错误。如果对拍通过了再把区间扩大到 [1, 100000] 这种中等范围对比一次暴力结果基本可以放心。5. 变种题与工程联想5.1 等差数的几种常见变体“等差数”这个概念的延伸能力很强常见变体有几种。第一种是“求第 K 个等差数”从小到大输出第 K 个满足条件的数。这种题通常用“二分答案 数位DP计数”来做对答案范围二分用 countArithmetic(mid) 判断 mid 之前有多少个等差数从而缩小范围。数位DP提供了一个 O(logR * 状态数) 的计数函数二分套上去完全可行。第二种是“回文等差数”要求一个数既是回文数又是等差数。这个约束很紧比如 12321 虽然是回文但它的差分序列是 1、1、-1、-1并不是等差数。真正常见的回文等差数其实是 111、222、333 这种公差为 0 的数以及 12321 这种需要特判的非等差回文。这种题更考“条件叠加”能力。第三种是把数字看成字符串允许删除若干位求能组成的最长等差数。这个就变成子序列DP了状态里除了公差还要记录长度复杂度会上一个台阶。但核心仍然是对“等差”这一性质的建模。5.2 等差数在实际业务里的应用场景很多人觉得这种题只在比赛里出现其实等差数在业务代码里也有用武之地。最典型的就是靓号识别手机号、车牌号、QQ号里12345、13579、24680 这种等差数会被当作靓号后台可以写一个类似 isArithmetic 的判断函数对号码打标或者做风控。第二个场景是验证码和优惠券生成有些运营活动故意生成等差数作为优惠码因为好记、辨识度高但副作用是太规律容易被批量猜中安全敏感场景必须避免。我在实际踩坑中遇到过一件事从数据库导出的一批测试账号 ID 全部是等差数一查发现是压测脚本为了“看起来规整”特意生成的 12345、23456 这类数字。如果当时没有这个判断逻辑可能要多花一晚上定位数据来源。所以这类小工具虽然简单放到工程里还挺实用。我个人这几年的体会是“等差数”这种小题非常适合拿来练数位DP。它比“不要62”多了一个公差状态又不像“数位和取模”那样抽象刚好卡在“够练基本功”的位置上。把这题的代码彻底写透前导零、公差映射、边界判断这三个能力基本就过关了。最后分享一个小技巧考试或者面试写这类题先别急着上数位DP花两分钟把暴力版写完哪怕只是用来对拍心态也会稳很多。