6957. 统计范围内的步进数字数目
题目描述：给你两个正整数low和high，求闭区间[low, high]中的整数满足相邻数位之间差的绝对值都恰好为1的数量。答案需要对1e9 + 7取模。
思路：比较明显的数位dp，假设有solve(x)函数可以求区间(0, x)之间满足上述条件的整数数量，则最终答案为solve(high + 1) - solve(low)。下面来设计solve函数，首先定义状态\(f_{i, j}\)表示长度为\(i\)且首位为\(j\)的满足上述条件的整数数目，则易得状态\(f_{i, j}\)的转移方程如下：
\[f_{i, j} = f_{i - 1, j - 1} + f_{i - 1, j + 1}
\]
对于一个长度为\(n\)的正整数\(x\)，满足上述条件且小于\(x\)的正整数数量为：
\[\text{solve}(x) = \sum\limits_{i = 1}^{n - 1} \sum\limits_{j = 1}^{9} f_{i, j} + \sum\limits_{j = 1}^{x_n - 1} f_{n, j} + \sum\limits_{i = n - 1 \sim 1}\sum\limits_{j = 0}^{x_i - 1}
\begin{cases}
f_{i, j} & \; abs(j - x_i) == 1 \\
0 & abs(x_{k + 1} - x_{k}) \neq 1 (\forall i \leq k < n) \\
0 & \text{others}
\end{cases}
\]
时间复杂度：\(O(dn)\)，其中\(d\)表示单个数字的范围，此题中\(d = 10\)
空间复杂度：\(O(dn)\)，其中\(d\)表示单个数字的范围，此题中\(d = 10\)
参考代码：
class Solution {
public:
int countSteppingNumbers(string low, string high) {
const int mod = 1e9 + 7;
vector<vector<int>> f(101, vector<int>(10, 0));
for (int i = 0; i <= 9; ++i) {
f[1][i] = 1;
}
for (int i = 2; i <= 100; ++i) {
for (int j = 0; j <= 9; ++j) {
if (j - 1 >= 0) {
f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod;
}
if (j + 1 <= 9) {
f[i][j] = (f[i][j] + f[i - 1][j + 1]) % mod;
}
}
}
function<vector<int>(string&, int)> string_to_vector = [](string& s, int delta) -> vector<int> {
int n = s.size();
vector<int> nums(n);
reverse(s.begin(), s.end());
for (int i = 0; i < n; ++i) {
nums[i] = s[i] - '0';
}
nums[0] += delta;
nums.push_back(0);
for (int i = 0; i < n; ++i) {
nums[i + 1] += nums[i] / 10;
nums[i] %= 10;
}
if (nums.back() == 0) {
nums.pop_back();
}
return nums;
};
vector<int> up = string_to_vector(high, 1);
vector<int> lw = string_to_vector(low, 0);
function<int(vector<int>&)> solve = [&](vector<int>& nums) -> int {
int res = 0;
int n = nums.size();
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= 9; ++j) {
res = (res + f[i][j]) % mod;
}
}
for (int j = 1; j < nums.back(); ++j) {
res = (res + f[n][j]) % mod;
}
for (int i = n - 1; i >= 1; --i) {
for (int j = 0; j < nums[i - 1]; ++j) {
if (abs(j - nums[i]) == 1) {
res = (res + f[i][j]) % mod;
}
}
if (abs(nums[i] - nums[i - 1]) != 1) {
break;
}
}
return res;
};
return ((solve(up) - solve(lw)) % mod + mod) % mod;
}
};