LeetCode LeetCode 2801. 统计范围内的步进数字数目 C++实现
这道题是经典的数位 DP（Digit 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 <cmath>
using 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 -> 0999）
if (i >= 0) {
str[i]--;
}
// 去掉前导 0
if (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++) {
// 如果前面已经填了数字，需要满足步进条件：相邻数字差的绝对值为 1
if (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;
// 初始化记忆化数组为 -1
memset(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 数组以及递归调用的栈空间。