给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的步进数字数目
如果一个整数相邻数位之间差的绝对值都恰好是 1 ，那么这个数字被称为步进数字
请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目
1. 数位dp
本质上就是动态规划，只需记录位数和前一个数的状态，其后满足条件的个数是固定的
数位dp还要多记录一个受限状态，以及前面全为0的特殊处理状态
class Solution {
const int MOD = 1e9 + 7;
int calc(string &s) {//因为需要调用两次，所以单独计算某个数的步进数字个数
int m = s.length(), memo[m][10];
memset(memo, -1, sizeof(memo)); //初始化dp，记忆化搜索， -1 表示没有计算过
function<int(int, int, bool)> f = [&](int i, int pre, bool is_limit) -> int {
if (i == m)
return pre!=-1; //-1表示数字0，不合法
if (!is_limit && pre!=-1 && memo[i][pre] != -1)//记忆化搜索
return memo[i][pre];
int res = 0;
if (pre==-1) //前面全为0，当前位也可以选择0，从而直接跳过
res = f(i + 1, -1, false);
int up = is_limit ? s[i] - '0' : 9; // 枚举上限
int down = pre==-1?1:0;
for (; down <= up; down++) // 枚举要填入的数字d，枚举下限看有否存在前面全为0
if (pre==-1 || abs(down - pre) == 1) // 第一位数字随便填，其余必须相差 1
res = (res + f(i + 1, down, is_limit && down == up)) % MOD;
if (!is_limit && pre!=-1)
memo[i][pre] = res;
return res;
};
return f(0, -1, true); //初始下标为0，有前导零，受限
}
bool valid(string &s) {
for (int i = 1; i < s.length(); i++)
if (abs(int(s[i]) - int(s[i - 1])) != 1)
return false;
return true;
}
public:
int countSteppingNumbers(string low, string high) {
return (calc(high) - calc(low) + MOD + valid(low)) % MOD; // +MOD 防止算出负数
}
};
2. 模板
class Solution {
const int MOD = 1e9 + 7;
int calc(string &s) {
int m = s.length(), memo[m][10];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, bool, bool)> f = [&](int i, int pre, bool is_limit, bool is_num) -> int {
if (i == m)
return is_num; // is_num 为 true 表示得到了一个合法数字
if (!is_limit && is_num && memo[i][pre] != -1)
return memo[i][pre];
int res = 0;
if (!is_num) // 可以跳过当前数位
res = f(i + 1, pre, false, false);
int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
if (!is_num || abs(d - pre) == 1) // 第一位数字随便填，其余必须相差 1
res = (res + f(i + 1, d, is_limit && d == up, true)) % MOD;
if (!is_limit && is_num)
memo[i][pre] = res;
return res;
};
return f(0, 0, true, false);
}
bool valid(string &s) {
for (int i = 1; i < s.length(); i++)
if (abs(int(s[i]) - int(s[i - 1])) != 1)
return false;
return true;
}
public:
int countSteppingNumbers(string low, string high) {
return (calc(high) - calc(low) + MOD + valid(low)) % MOD; // +MOD 防止算出负数
}
};