题目描述：
给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。
如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
注意：步进数字不能有前导 0 。
数据范围：
$1\le int(low) \le int(high) \lt 10^{100}$
题解：
答案需要取模，跟相邻不能相同差不多，直接数位dp。需要注意的是，如果存在前导零，那么第一位可以填任意值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
string s;
int len;
long long dp[100][10];
long long dfs(int step, int pre, bool isLimit, bool isLead)
{
if (step == len)
return !isLead;
if (!isLimit && !isLead && dp[step][pre] != -1)
return dp[step][pre];
long long ans = 0;
if (isLead)
ans = (ans + dfs(step + 1, pre, false, true)) % mod;
int up = isLimit ? s[step] - '0' : 9;
for (int i = isLead; i <= up; ++i)
{
if (!isLead && abs(i - pre) != 1)
continue;
ans = (ans + dfs(step + 1, i, isLimit && i == up, false)) % mod;
}
if (!isLimit && !isLead)
dp[step][pre] = ans;
return ans;
}
long long solve(string upper)
{
memset(dp, -1, sizeof(dp));
s = upper;
len = s.length();
return dfs(0, 0, true, true);
}
int countSteppingNumbers(string low, string high)
{
long long ret1 = solve(high);
long long ret2 = solve(low);
bool flag = true;
for (int i = 1; i < low.length(); ++i)
{
if (abs(low[i] - low[i - 1]) != 1)
{
flag = false;
break;
}
}
ret2 -= flag;
return (ret1 - ret2 + mod) % mod;
}
};
|