LeetCode LeetCode 2801. 统计范围内的步进数字数目 C++实现

这道题是经典的数位 DPDigit DP问题。我们可以直接沿用之前 Java 实现的记忆化搜索思路将其转化为 C 代码。核心思路1. 前缀和思想将求解闭区间 [low, high] 转化为 count(high) - count(low - 1)。2. 记忆化搜索DFS* 使用 dfs(pos, prevDigit, isLimit, isNum) 从高位向低位枚举。* pos当前遍历到的数位下标。* prevDigit上一位填入的数字用于判断相邻数位差的绝对值是否为 1。* isLimit当前位是否受上界字符串的限制。* isNum前面是否已经填入了非零的有效数字用于处理前导 0。3. 字符串减一操作由于 low 和 high 的长度可达 100必须使用字符串来模拟大数减 1 的操作以避免整数溢出。C 代码实现#include vector#include string#include cstring#include cmathusing namespace std;class Solution {private:static const int MOD 1000000007;string s;// 记忆化数组[位置][上一位数字(0-9)][是否受限制][前面是否已填数字]// 上一位数字用 10 表示初始状态前面没有数字int memo[105][11][2][2];// 字符串模拟数字减 1处理 low - 1避免大数溢出string subtractOne(string str) {int i str.length() - 1;// 从最后一位开始借位while (i 0 str[i] 0) {str[i] 9;i--;}// 如果还没减完比如 1000 - 0999if (i 0) {str[i]--;}// 去掉前导 0if (str[0] 0 str.length() 1) {return str.substr(1);}return str;}// 计算从 0 到字符串 s 代表的数字之间有多少个步进数字long long dfs(int pos, int prevDigit, bool isLimit, bool isNum) {// 递归终止条件已经填完所有位置if (pos s.length()) {// 如果前面填了有效数字说明找到了一个合法的步进数字return isNum ? 1 : 0;}// 如果该状态已经计算过直接返回if (memo[pos][prevDigit][isLimit][isNum] ! -1) {return memo[pos][prevDigit][isLimit][isNum];}long long res 0;// 确定当前位能填入的最大数字int up isLimit ? s[pos] - 0 : 9;// 1. 处理前导 0 的情况如果前面还没填数字当前位可以继续填 0跳过if (!isNum) {res (res dfs(pos 1, 10, false, false)) % MOD;}// 2. 枚举当前位填入的数字 d// 起始数字如果前面没填数字(!isNum)从1开始否则从0开始int start isNum ? 0 : 1;for (int d start; d up; d) {// 如果前面已经填了数字需要满足步进条件相邻数字差的绝对值为 1if (isNum abs(d - prevDigit) ! 1) {continue;}// 递归进入下一位res (res dfs(pos 1, d, isLimit d up, true)) % MOD;}// 记录并返回结果memo[pos][prevDigit][isLimit][isNum] res;return res;}long long count(string str) {s str;// 初始化记忆化数组为 -1memset(memo, -1, sizeof(memo));return dfs(0, 10, true, false);}public:int countSteppingNumbers(string low, string high) {// 计算 [0, high] 的步进数字个数long long countHigh count(high);// 计算 [0, low-1] 的步进数字个数long long countLow count(subtractOne(low));// 结果为两者之差注意取模防止负数return (int)((countHigh - countLow MOD) % MOD);}};复杂度分析* 时间复杂度O(log N)其中 N 是 high 的数值。数位 DP 的状态数取决于数字的位数最多 100 位、上一位数字0-9共11种状态、是否受限2种和是否已填数字2种。总状态数非常少每次转移最多枚举 10 个数字因此效率极高。* 空间复杂度O(log N)主要用于存储记忆化搜索的 memo 数组以及递归调用的栈空间。