统计范围内的步进数字数目

風月无关我 / 2023-07-30 / 原文

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;
    }
};

类似题：P2657 SCOI2009 windy 数