这道题是一道非常经典的数位 DPDigit DP问题。核心思路步进数字的定义是相邻两个数字之差的绝对值恰好为 1。如果直接用暴力法遍历 low 到 high 之间的每一个数去判断在数据范围极大比如 10^{18}时会直接超时。我们可以利用前缀和思想将问题转化为结果 (0 到 high 的步进数字个数) - (0 到 low-1 的步进数字个数)接下来我们只需要实现一个函数 countSteppingNumbers(String s)用来计算从 0 到字符串 s 代表的数字之间有多少个步进数字。这里采用记忆化搜索Memoization来实现数位 DP1. 状态定义dfs(pos, prevDigit, isLimit, isNum)* pos当前处理到第几位从左到右。* prevDigit上一位填入的数字用于判断当前位能否满足步进条件。* isLimit当前位是否受到上界 s 的限制如果前面几位都和 s 一样当前位就不能超过 s[pos]。* isNum前面是否已经填入了有效数字用于处理前导 0 的情况比如数字 05 其实是 5。2. 转移逻辑* 如果 isNum 为 false前面全是前导 0当前位可以选择跳过继续填 0或者填入 1-9 作为起始数字。* 如果 isNum 为 true当前位填入的数字 d 必须满足 Math.abs(d - prevDigit) 1。Java 代码实现import java.util.Arrays;class Solution {private static final int MOD 1000000007;private char[] digits;private Integer[][][][] memo;public int countSteppingNumbers(String low, String high) {// 计算 [0, high] 的步进数字个数long countHigh count(high);// 计算 [0, low-1] 的步进数字个数long countLow count(subtractOne(low));// 结果为两者之差注意取模防止负数return (int) ((countHigh - countLow MOD) % MOD);}// 计算从 0 到字符串 s 代表的数字之间有多少个步进数字private long count(String s) {digits s.toCharArray();int n digits.length;// 记忆化数组[位置][上一位数字(0-9)][是否受限制][前面是否已填数字]// 上一位数字用 10 表示初始状态前面没有数字memo new Integer[n][11][2][2];return dfs(0, 10, 1, 0);}private long dfs(int pos, int prevDigit, int isLimit, int isNum) {// 递归终止条件已经填完所有位置if (pos digits.length) {// 如果前面填了有效数字说明找到了一个合法的步进数字return isNum 1 ? 1 : 0;}// 如果该状态已经计算过直接返回if (memo[pos][prevDigit][isLimit][isNum] ! null) {return memo[pos][prevDigit][isLimit][isNum];}long res 0;// 确定当前位能填入的最大数字int up isLimit 1 ? digits[pos] - 0 : 9;// 1. 处理前导 0 的情况如果前面还没填数字当前位可以继续填 0跳过if (isNum 0) {res (res dfs(pos 1, 10, 0, 0)) % MOD;}// 2. 枚举当前位填入的数字 d// 起始数字如果前面没填数字(isNum0)从1开始否则从0开始int start isNum 0 ? 1 : 0;for (int d start; d up; d) {// 如果前面已经填了数字需要满足步进条件相邻数字差的绝对值为 1if (isNum 1 Math.abs(d - prevDigit) ! 1) {continue;}// 递归进入下一位// 新的 isLimit只有当前位受限制且填了最大值时下一位才受限制int nextIsLimit (isLimit 1 d up) ? 1 : 0;res (res dfs(pos 1, d, nextIsLimit, 1)) % MOD;}// 记录并返回结果memo[pos][prevDigit][isLimit][isNum] (int) res;return res;}// 字符串模拟数字减 1处理 low - 1避免大数溢出private String subtractOne(String s) {char[] chars s.toCharArray();int i chars.length - 1;// 从最后一位开始借位while (i 0 chars[i] 0) {chars[i] 9;i--;}// 如果减到了最前面比如 1000 - 0999且首位变成了 0if (i 0) {chars[i]--;}// 如果首位变成了 0且原字符串长度大于1去掉前导 0if (chars[0] 0 chars.length 1) {return new String(chars, 1, chars.length - 1);}return new String(chars);}}复杂度分析* 时间复杂度O(log N)其中 N 是 high 的数值。数位 DP 的状态数取决于数字的位数最多 100 位、上一位数字0-9共11种状态、是否受限2种和是否已填数字2种。总状态数非常少每次转移最多枚举 10 个数字因此效率极高。* 空间复杂度O(log N)主要用于存储记忆化搜索的 memo 数组以及递归调用的栈空间。